Minimum Falling Path Sum II - Leetcode 1289 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/minimum...
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

[@bhuvan9956]

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

[@corrogist692]

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

[@pratikpatel2512]

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]

[@samridhshubham8109]

NEAT!!

[@udemezueiloabachie8626]

This is the neatest solution in 6 lines: class Solution: def minFallingPathSum(self, grid: List[List[int]]) -> int: size = len(grid) for r in range(size - 2, -1, -1): for c in range(size): grid[r][c] = grid[r][c] + min(grid[r + 1][:c] + grid[r + 1][c + 1:]) return min(grid[0])

[@MP-ny3ep]

Thank you so much. Been waiting for this one.

[@business_central]

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

[@tawfikkoptan5781]

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

[@kebab4640]

Thanks sir!

[@satyamjha68]

Solved it!!

[@meemee417]

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

[@kahafb]

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

[@chien-yuyeh9386]

Nice🎉🎉

[@advaitdongre4499]

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?

[@dampdigits]

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

[@akialter]

DP week

[@pastori2672]

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

[@ik6071]

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

[@nikhil199029]

U impemented priority queue with size 2.

[@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]

[@chaitanyasharma6270]

I dont get TLE with the caching solution in java

[@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?

[@NeetCodeIO]

Shit you're right

[@michael._.]

@@NeetCodeIO i always wanted to tell you, it’s not just about solutions, but I always learned how to explain a problem comprehensively from your videos and it helped me so much, thank you :>

[@AkshayAnil0-1]

Yes

[@TF2Shows]

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?

[@kebab4640]

Finally lol

[@leedinglin7482]

flfc

[@carrotiq6879]

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

[@hasrat17]

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.