Minimum Path Sum

Minimum Path Sum in a Grid

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.

Naive Solution (Brute Force)

The brute force solution would involve exploring every possible path from the top-left corner to the bottom-right corner. This can be done recursively. At each cell, we have two choices: move down or move right. We explore both possibilities and return the minimum sum among all paths.

Code (Python)

def min_path_sum_brute_force(grid):
    def solve(row, col):
        if row == len(grid) - 1 and col == len(grid[0]) - 1:
            return grid[row][col]
        
        if row >= len(grid) or col >= len(grid[0]):
            return float('inf')
        
        return grid[row][col] + min(solve(row + 1, col), solve(row, col + 1))
    
    return solve(0, 0)

Time Complexity

The time complexity is exponential, O(2^(m+n)), because in the worst case, we explore every possible path.

Space Complexity

The space complexity is O(m+n) due to the depth of the recursion stack.

Optimal Solution (Dynamic Programming)

Dynamic programming can be used to solve this problem efficiently. We can create a DP table dp of the same dimensions as the input grid. dp[i][j] will store the minimum path sum from the top-left corner to cell (i, j). We can populate the dp table as follows:

1. Initialize dp[0][0] with grid[0][0].
2. For the first row, dp[0][j] = dp[0][j-1] + grid[0][j].
3. For the first column, dp[i][0] = dp[i-1][0] + grid[i][0].
4. For the remaining cells, dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Finally, dp[m-1][n-1] will contain the minimum path sum from the top-left to the bottom-right.

Code (Python)

def min_path_sum_dp(grid):
    m = len(grid)
    n = len(grid[0])
    
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    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]

Time Complexity

The time complexity is O(m*n) because we iterate through each cell in the grid once.

Space Complexity

The space complexity is O(m*n) because we use a DP table of the same dimensions as the grid.

Space Optimization

We can optimize the space complexity to O(n) by using only one row to store the DP values. We iterate over the rows and update the current row based on the previous row.

def min_path_sum_dp_optimized(grid):
    m = len(grid)
    n = len(grid[0])

    dp = [0] * n

    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[j] = grid[i][j]
            elif i == 0:
                dp[j] = dp[j-1] + grid[i][j]
            elif j == 0:
                dp[j] = dp[j] + grid[i][j]
            else:
                dp[j] = grid[i][j] + min(dp[j-1], dp[j])

    return dp[n-1]

Optimized Space Complexity

The time complexity remains O(m*n), but the space complexity is now O(n).

Edge Cases

• Empty grid: If the grid is empty (m=0 or n=0), return 0 or handle it based on problem requirement. In some cases an exception should be thrown.
• Single cell grid: If the grid has only one cell (m=1 and n=1), return the value of that cell.
• Grid with zero values: The algorithm should work correctly even if some grid cells have values of zero.