64. Minimum Path Sum


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.

Example 1:

[[1,3,1],
 [1,5,1],
 [4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.


Summary

We have to find the minimum sum of numbers over a path from the top left to the bottom right of the given matrix .

Solution

Approach #1 Brute Force [Time Limit Exceeded]

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 a right step or downward step to minimize the sum.

Complexity Analysis

  • Time complexity : . For every move, we have atmost 2 options.
  • Space complexity : . Recursion of depth .

Approach #2 Dynamic Programming 2D [Accepted]

Algorithm

We use an extra matrix of the same size as the original matrix. In this matrix, represents the minimum sum of the path from the index to the bottom rightmost element. We start by initializing the bottom rightmost element of as the last element of the given matrix. Then for each element starting from the bottom right, we traverse backwards and fill in the matrix with the required minimum sums. Now, we need to note that at every element, we can move either rightwards or downwards. Therefore, for filling in the minimum sum, we use the equation:

, taking care of the boundary conditions.

The following figure illustrates the process: !?!../Documents/64_Minimum_Path_Sum.json:859,390!?!

Complexity Analysis

  • Time complexity : . We traverse the entire matrix once.

  • Space complexity : . Another matrix of the same size is used.

Approach #3 Dynamic Programming 1D [Accepted]

Algorithm

In the previous case, instead of using a 2D matrix for dp, we can do the same work using a array of the row size, since for making the current entry all we need is the dp entry for the bottom and the right element. Thus, we start by initializing only the last element of the array as the last element of the given matrix. The last entry is the bottom rightmost element of the given matrix. Then, we start moving towards the left and update the entry as:

We repeat the same process for every row as we move upwards. At the end gives the required minimum sum.

Complexity Analysis

  • Time complexity : . We traverse the entire matrix once.

  • Space complexity : . Another array of row size is used.

Approach #4 Dynamic Programming (Without Extra Space) [Accepted]

Algorithm

This approach is same as Approach 2, with a slight difference. Instead of using another matrix. We can store the minimum sums in the original matrix itself, since we need not retain the original matrix here. Thus, the governing equation now becomes:

Complexity Analysis

  • Time complexity : . We traverse the entire matrix once.

  • Space complexity : . No extra space is used.

Analysis written by: @vinod23

Submit Solution