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]
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])
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
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?
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]
@@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 :>
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?
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.
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]
NEAT!!
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])
I used basically the same approach, but modified the grid in place top-down. Seems even less code and easier to understand!
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
Dude... you are such a Hero! 🔥🔥🔥🔥
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])
Yes this is easier than the previous one. At least when it comes to being naive about time complexity.
Thank you so much. Been waiting for this one.
This is the first 30+ minute video om a problem I've seen you make 😂😂😂
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
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]
Thanks sir!
Solved it!!
Nice🎉🎉
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
in the last solution, doesn't the line:
`first_row = [(val, idx) for idx, val in enumerate(grid[0])]`
require $O(n)$ space complexity?
Shit you're right
@@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 :>
Yes
DP week
I dont get TLE with the caching solution in java
U impemented priority queue with size 2.
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.