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])
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?
@@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 :>
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]
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.