algoadvance

You are given an m x n grid filled with non-negative numbers, representing a cost grid where you need to find a path that minimizes the cost from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1). You can only move either down or right at any point in time.

The task is to determine the minimum path sum.

Example:

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.

Clarifying Questions

  1. Q: Can the values in the grid be zero?
    • A: Yes, the values can be zero but they are non-negative.
  2. Q: Are we guaranteed that the grid has at least one row and one column?
    • A: Yes, the input will be a non-empty grid.

Strategy

This is a classic dynamic programming problem where we need to find the minimum cost path from the top-left to the bottom-right cell. The approach will be as follows:

  1. Initialization:
    • Create a 2D list dp where dp[i][j] represents the minimum path sum to reach cell (i, j).
  2. Base Case:
    • The cost to reach the starting cell (0, 0) is just the value of that cell: dp[0][0] = grid[0][0].
  3. DP Transition:
    • For the first row and the first column, the only way to reach these cells is from their left (for row) or top (for column).
    • For all other cells (i, j), we can arrive either from the left (i, j-1) or from above (i-1, j).
    • Thus, dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
  4. Result:
    • The value at dp[m-1][n-1] will give us the minimum path sum from the top-left to the bottom-right cell.

Time Complexity

Code

def minPathSum(grid):
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    # Initialize first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Initialize first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # Fill the dp table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[m-1][n-1]

In this implementation, we fill out a dynamic programming table that records the minimum path sum to each cell (i, j). By the time we process all cells, we can return the value at the last cell for the final minimum path sum.

Try our interview co-pilot at AlgoAdvance.com