Minimum Falling Path Sum II - Leetcode 1289 - Python 

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

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]

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

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

Funny in-place solution class Solution: def minFallingPathSum(self, grid: List[List[int]]) -> int: n = len(grid) def helper(i): first, second, idx = inf, inf, None for j, val in enumerate(grid[i]): if val < first: second = first first = val idx = j elif val < second: second = val return (first, second, idx) for i in range(n-2, -1, -1): first, second, idx = helper(i+1) for j in range(n): if j != idx: grid[i][j] += first else: grid[i][j] += second return min(grid[0])

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?

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

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

Dude... you are such a Hero! 🔥🔥🔥🔥

in the last solution, doesn't the line: `first_row = [(val, idx) for idx, val in enumerate(grid[0])]` require $O(n)$ space complexity?

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]

Thank you so much. Been waiting for this one.

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

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

Thanks sir!

Solved it!!

Nice🎉🎉

I dont get TLE with the caching solution in java

U impemented priority queue with size 2.

DP week

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?

Finally lol

flfc

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

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.