Minimum Falling Path Sum II - Leetcode 1289 - Python

0:00 - Read the problem
1:29 - Drawing Recursive
4:37 - Coding Recursive
9:09 - Drawing DP
14:50 - Coding DP
17:44 - Drawing Optimized DP
23:17 - Coding Optimized DP

leetcode 1289

#neetcode #leetcode #python

[bhuvan]

Love the longer videos. Basically helps me to see the entire picture. Please keep it going. Love you!

[pratikpatel]

A simple and more neat code:

class Solution:
def minFallingPathSum(self, grid: List[List[int]]) -> int:

N = len(grid)

def get_min_two(r):
min1, min2 = float('inf'), float('inf')
min1_idx, min2_idx = -1, -1
for c in range(N):
if grid[r][c] <= min1:
min2, min1 = min1, grid[r][c]
min2_idx, min1_idx = min1_idx, c
elif grid[r][c] < min2:
min2, min2_idx = grid[r][c], c
return [(min1, min1_idx), (min2, min2_idx)]

for r in range(1, N):
min_dp = get_min_two(r - 1)
for c in range(N):
grid[r][c] += min_dp[0][0] if min_dp[0][1] != c else min_dp[1][0]

return min(grid[N-1])

[corrogist]

I used basically the same approach, but modified the grid in place top-down. Seems even less code and easier to understand!

[DankMemes-xqxm]

After getting to 14:30 or so, I stopped the video and came up with this solution:

class Solution:
def minFallingPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
row1 = grid[0]
if n == 1:
return grid[0][0]

for r in range(1, n):
row2 = grid[r]
for c in range(len(row2)):
left_min = min(row1[:c] or [float('inf')])
right_min = min(row1[c+1:] or [float('inf')])
row2[c] += min(left_min, right_min)
row1 = row2

return min(row2)

This is the first time I was able to code up a solution for a DP problem without looking at your code :D

[tawfikkoptan]

This is the first 30+ minute video om a problem I've seen you make 😂😂😂

[aashishbathe]

I am seeing this entire video after a long time, if anyone wants a more code optimized solution for last method, here it is :)
class Solution:
def minFallingPathSum(self, grid: List[List[int]]) -> int:
def find_smallest(row):
smallest = []
for idx, num in enumerate(row):
if len(smallest) < 2:
smallest.append((num, idx))
elif smallest[1][0] > num:
smallest.pop()
smallest.append((num, idx))
smallest.sort()
return smallest

N = len(grid)
dp = find_smallest(grid[0])
for r in range(1, N):
new_dp = []
new_row = grid[r]
for next_c in range(N):
if next_c == dp[0][1]:
new_row[next_c] += dp[1][0]
else:
new_row[next_c] += dp[0][0]
new_dp = find_smallest(new_row)
dp = new_dp
return dp[0][0]

[dampdigits]

Yes this is easier than the previous one. At least when it comes to being naive about time complexity.

[meemee]

Did the same thing but with heap to get min 2 nums and their indices without using a helper function

[MP-nyep]

Thank you so much. Been waiting for this one.

[advaitdongre]

but at line 26, we're using the helper function right? what is the time complexity gets to bigO(n^3)? since the function is already using a for loop and then we're using it inside 2 for loops?

[pastori]

idk what it is but this is much easier then minimum height trees imo

[nikhil]

U impemented priority queue with size 2.

[ik]

why use tuple? and not a dict to store element-> idx for two minimum pairs?

[TFShows]

Can someone help? (WARNING: solution incoming, don't read if you haven't solved it yet) I'm using the O(n^2) runtime and O(1) memory solution, in which in find 1st and 2nd minimum in each row.

I wrote my implementation but got stuck in test case 9:

[-37, 51, -36, 34, -22],
[82, 4, 30, 14, 38],
[-68, -52, -92, 65, -85],
[-49, -3, -77, 8, -19],
[-60, -71, -21, -62, -73]
The greedy path is: -37, 4, -92, -49, -73 for a total of -247.

But the test case expected answer is: -268 which is the path: -37, 4, -85, -77, -73.

Can someone explain why the greedy solution, which should work, doesn't work in this case? Why im the only one that fails this test case?

[michael._.]

in the last solution, doesn't the line:

`first_row = [(val, idx) for idx, val in enumerate(grid[0])]`

require $O(n)$ space complexity?

[reinventingdwheel]

I dont get TLE with the caching solution in java

[carrotiq]

pls don't do TOP DOWN solution, By watching your videos I have train my brain to first think of Bottom-up solution, and it has become a habit. So continue with good old Bottom-up

[hasrat]

Thanks, Can you give me referrel? I am actively looking for a Job last year I completed my degree and joined HCLTech but I didn't like working there so I resigned this month.