We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Path Sum

Difficulty: Medium

Problem Description

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. You can only move either down or right at any point in time.

Key Insights

  • The problem can be solved using Dynamic Programming.
  • We only need to keep track of the minimum path sum to reach each cell.
  • The only allowed movements are down or right, which simplifies the state transition.
  • The grid can be modified in place to save space, or a separate DP array can be used.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1) or O(n) (depending on whether we use in-place modification or a 1D array)

Solution

The approach utilizes Dynamic Programming to compute the minimum path sum to each cell in the grid. We iterate through each cell, calculating the minimum path sum to that cell by considering the sums from the cell above it and the cell to the left of it. The final answer will be found in the bottom-right cell of the grid.

  1. Start from the top-left corner of the grid.
  2. For each cell, the minimum path sum to that cell is the value of the cell plus the minimum of the path sums of the cell above it and the cell to the left.
  3. Update the grid in place to reflect the minimum path sums.
  4. Return the value in the bottom-right corner of the grid as the result.

Code Solutions

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue  # Do nothing for the starting cell
            top = grid[i - 1][j] if i > 0 else float('inf')
            left = grid[i][j - 1] if j > 0 else float('inf')
            grid[i][j] += min(top, left)  # Update current cell with the minimum path sum
    return grid[-1][-1]  # Return the bottom-right cell value
← Back to All Questions