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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Path Sum

Number: 64

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Goldman Sachs, Microsoft, Nvidia, Meta, Palo Alto Networks, Uber, TikTok, Bloomberg, Apple, eBay

Problem Description

Given an m x n grid filled with non-negative numbers, find a path from the top-left cell to the bottom-right cell that minimizes the sum of all numbers along its path. You can only move either down or right at any point.

Key Insights

  • The problem can be solved using Dynamic Programming.
  • The optimal solution for each cell depends on the minimum path sum of the cell above it and the cell to its left.
  • Since you can only move right or down, only two adjacent cells affect the current cell's result.
  • Edge cases include the first row and first column, which have only one direction of movement.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the number of rows and columns. Space Complexity: O(m * n) for the DP table (this can be optimized to O(n) with in-place computations).

Solution

We use a Dynamic Programming (DP) approach where we create a DP table (or use the grid itself) that stores the minimum path sum to each cell. For each cell (i, j):

  1. If i = 0 (first row), the only possible path is from the left.
  2. If j = 0 (first column), the only possible path is from above.
  3. For other cells, the minimum path sum is the cell value plus the minimum of the two possible previous cells (above and left). This ensures that by the time we reach the bottom-right cell, we have accumulated the minimum sum required to reach that cell.

Code Solutions

# Python solution using dynamic programming
def minPathSum(grid):
    # Number of rows and columns in the grid
    rows = len(grid)
    cols = len(grid[0])
    
    # Initialize the DP table directly in grid to save space
    # Fill the first row by accumulating the sum from the left
    for j in range(1, cols):
        grid[0][j] += grid[0][j-1]
        
    # Fill the first column by accumulating the sum above
    for i in range(1, rows):
        grid[i][0] += grid[i-1][0]
    
    # Compute the minimum path sum for the rest of the cells
    for i in range(1, rows):
        for j in range(1, cols):
            # The cell value is added to the minimum of the top or left cell
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    
    # The bottom-right cell contains the answer
    return grid[rows-1][cols-1]

# Example usage
example_grid = [[1,3,1],[1,5,1],[4,2,1]]
print(minPathSum(example_grid))  # Output should be 7
← Back to All Questions