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.

For example, consider the grid:

grid = [[1,3,1],[1,5,1],[4,2,1]]

What is the minimum path sum from the top-left (grid[0][0]) to the bottom-right (grid[2][2])? The answer is 7, because the path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

As another example:

grid = [[1,2,3],[4,5,6]]

What is the minimum path sum in this grid? The answer is 12.

Outline an algorithm to efficiently find the minimum path sum in a given grid with the constraint that you can only move down or right. What is the time and space complexity of your solution?

Minimum Path Sum in a Grid

Problem Description

Given a m x n grid filled with non-negative numbers, the goal is to find a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along the path. The constraint is that 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: The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2:

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

Solution

We can solve this problem using dynamic programming. We'll create a DP table of the same size as the grid, where dp[i][j] represents the minimum path sum from the top-left corner to cell (i, j). The base case is dp[0][0] = grid[0][0]. We can then fill the DP table iteratively, using the following recurrence relation:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

where dp[i-1][j] is the minimum path sum to the cell above, and dp[i][j-1] is the minimum path sum to the cell to the left. We'll handle the edge cases where i-1 or j-1 are out of bounds by setting the corresponding value to infinity (or a very large number) so that they don't affect the min calculation.

Here's the Python code:

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = grid[0][0]

    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            up = dp[i-1][j] if i > 0 else float('inf')
            left = dp[i][j-1] if j > 0 else float('inf')
            dp[i][j] = grid[i][j] + min(up, left)

    return dp[m-1][n-1]

Brute Force Solution

A brute-force approach would involve exploring all possible paths from the top-left to the bottom-right corner using recursion. However, this approach has exponential time complexity and would result in a Time Limit Exceeded (TLE) error for larger grids.

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

Big(O) Runtime Analysis

• The dynamic programming solution has a time complexity of O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because we iterate through each cell in the grid once to fill the DP table.
• The brute force solution has exponential time complexity, as it explores all possible paths. Specifically, it's O(2^(m+n)), although a more precise upper bound could be calculated with combinatorics.

Big(O) Space Usage Analysis

• The dynamic programming solution uses O(m * n) space to store the DP table.
• The brute force solution uses O(m + n) space due to the recursion depth. In the worst case, the call stack can grow to a depth of m + n.

Edge Cases

1. Empty Grid: If the grid is empty (either m or n is 0), we should return 0 (or possibly raise an exception, depending on the problem requirements).
2. Single Cell Grid: If the grid has only one cell, the minimum path sum is simply the value of that cell.
3. Grid with Zeroes: The algorithm handles grids with zeroes correctly, as the min function will correctly choose the path with the smallest sum, even if some cells have a value of 0.
4. Grid with Large Values: If the grid contains very large values, we should ensure that the intermediate sums don't overflow. In languages like Python, this is less of a concern, but in languages like Java or C++, we might need to use larger integer types (e.g., long).