In this series, I am going to solve Leetcode medium problems live with my friends, which you can see on our youtube channel. Today we will do Problem Leetcode: 64. Minimum Path Sum
A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time
Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Input: grid = [[1,2,3],[4,5,6]] Output: 12
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
The Brute Force approach involves recursion. For each element, we consider two paths, rightwards and downwards, and find the minimum sum out of those two. It specifies whether we need to take the right step or a downward step to minimize the sum.
cost(i, j) = grid[i][j] + min(cost(i+1, j), cost(i, j+1))
The following code implements this algorithm:
The time complexity is O(2^(m+n))
The time complexity is O(m+n)
The idea is to calculate, for each index(i, j) find the min path from the top left to the index (i, j).
First Row and Column Cases
In the first row, we can move only right, and hence to reach any index in the first row the min path sum is the sum of all elements from the top left to that index.
For the first column, we can move only down, and hence to reach any index in the first row the min path sum is the sum of all elements from the top left to that index.
Any other Case
Now to reach index (i, j) we have two options
we reach from the index (i-1,j)
or we reach from the index (i, j-1)
We will choose the minimum of these two indexes. If we apply the same intuition for the rest of the grid we will find the min path sum from the top left to right bottom.
The time complexity is O(n*m)
The space complexity is O(1)