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!

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

Thank you so much. Been waiting for this one.

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])

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

Thanks sir!

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

Solved it!!

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

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])

Nice🎉🎉

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

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

DP week

I dont get TLE with the caching solution in java

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

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

U impemented priority queue with size 2.

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]