Google Medium Dynamic Programming Problem - Leetcode 64 - Minimum Path Sum

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[Krokodil]

This feels like a simpler version of Dijkstra's right?

[nclsDesign]

They love this because that's basically how Google Maps' navigation algorithm works

[BederikStorm]

If all numbers are positive, You can even use positive/negative numbers to store where did you come from to restore the path

[MyCodingDiary]

Your videos always make my day. Keep shining!

[vedanshagarwal]

I submitted just after listening to this approach and got accepted at once ❤

[stuartreynolds]

It’s hugely faster if you start from the end. And hugely faster if you add on an estimate of the distance to the endpoint and pick the best estimated path next.

[yanivka]

…. O(n) when n is the amount of cells. Your algo is not optimal at all, in big board cases you will have the option to skip cells that have values higher then other that may be in the path to the target point.
Using the A* algo here would be optimal, when the fitness function is the total sum + amount of jumps to get to the target cell (this is calculated for each option we have to move starting from the first cell) This would have been considered optimal.

[galtbarber]

Dynamic programming is used in sequence alignments like RNA aligned to (homologous) DNA.

[zhongzhong]

Basically a oversimplified version of google map route recommendation algorithm

[budddwyer]

exactly the same problem can be found in the Unified State Exam, the main exam for schoolchildren in Russia entering university, and it can be easily solved in Excel. but we also have some walls or even teleportation

[andrei_camilotto]

Graph problem. Can be solved with dijkstra algorithm since it doesn't have negative values

[ARkhan-xwud]

class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])

dp = [[0]*n for _ in range(m)]

dp[0][0] = grid[0][0] # initialize first cell

for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0] # initialize first column

for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j] # initialize first row

for i in range(1, m): # rest dp table
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

return dp[m-1][n-1]




I find this more easier O(m*n) time complexity

[mjp]

I have never undestood why these kind of problems are part of an interview. If it is "very common" then the solution can be looked up and everything you are testing for is whether the applicant can memorize the solution.
Of course I am extremely bad at these kinds of tests, so it might all be a case of sour grapes 😄

[MrBot-jbsj]

Why do you write your twos like mirrored 6-es 😭 What did 2 ever do to you, sir?

[Kosorith]

"We're only allowed to go right or down" Oh, I see, I've initially missed this assumption. The algorithm doesn't work if we could move left/up like you normally would when looking for a minimum path.

[its_Khoa]

Minimum path, what if we have to actually return an array of steps to the destination, how would that be solve

[ndchunter]

i guess it works when you can rely on being in the top left corner and the goal in the bottom right but it doesn't track the path you took but the cost. you could add simply storing the i, j value in the if clauses, but how about making it more versatile by checking for visited and reachable coordinates and only processing them

[sonnyhe]

What i dont get is that the result returns a grid. How is a grid telling me the shortest path?
Like if someone gives me a solution of a 100 by 100 grid and say that is the answer, wouldnt i still have to write an algo to decipher the path in that shortest path grid?

[subirdas]

It’s optimized for early weight bias !