Problem 22 - Minimum Path Sum

Explore our archive for previous posts.

Question

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:

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.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 200

• 0 <= grid[i][j] <= 200

Approach

The solution uses dynamic programming to calculate the minimum path sum in a grid. Each cell’s value will essentially represent the minimum path sum to reach that particular cell. To do so, we iteratively build the grid, updating each cell's value to represent the minimum path sum from the top and left cells. By considering adjacent cells and taking the minimum path sum, it efficiently determines the minimum path sum for the entire grid.

Here's a high-level explanation of the solution:

1. We start by iterating over the first row of the grid and updating each cell's value to represent the minimum path sum from the top and left cells to that cell. For the first row, you can only arrive at a particular cell from it’s left neighbor cell.

2. Similarly, we iterate over the first column of the grid and update each cell's value to represent the minimum path sum from the top and left cells to that cell. For the first column, you can only arrive at a particular cell from it’s top neighbor cell.

3. Next, we iterate over the remaining cells of the grid (excluding the first row and column). For each cell, we calculate the minimum path sum to reach that cell by taking the minimum of the path sum from the cell above and the path sum from the cell to the left. We add this minimum value to the current cell's value.

4. Finally, we return the value in the bottom-right cell of the grid, which represents the minimum path sum from the top-left cell to the bottom-right cell.

Solution

Solve it here

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length; // Number of rows
        int n = grid[0].length; // Number of columns
        
        // Calculate the minimum path sum for the first row
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        
        // Calculate the minimum path sum for the first column
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        
        // Calculate the minimum path sum for each cell based on the previous adjacent cells
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        // Return the minimum path sum for the last cell
        return grid[m - 1][n - 1];
    }
}

Time and space complexity

Time Complexity: The time complexity of this solution is O(m * n), where 'm' is the number of rows and 'n' is the number of columns in the grid. The algorithm iterates through each cell of the grid exactly once, which requires nested loops with 'm' and 'n' iterations.

Space Complexity: The space complexity is O(1) since the algorithm modifies the input grid in-place without using any additional data structures that grow with the input size. Therefore, the space usage remains constant regardless of the grid size.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!