Minimum Path Sum Interview Question for Google

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 a grid like this:

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

The minimum path sum in this grid is 7, achieved by the path 1 -> 3 -> 1 -> 1 -> 1.

As another example, consider this grid:

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

In this case, the minimum path sum is 12.

Your task is to implement an algorithm that efficiently finds this minimum path sum for any given m x n grid of non-negative numbers, subject to the constraint that you can only move down or right at each step.

# Minimum Path Sum

This problem asks us to find the minimum path sum from the top-left corner to the bottom-right corner of a grid, where we can only move down or right. This is a classic dynamic programming problem.

## Naive Solution (Recursion)

A naive approach would be to use recursion. We can define a recursive function `minPathSum(i, j)` that returns the minimum path sum from `(0, 0)` to `(i, j)`.  The base case would be when `i` and `j` are both 0, in which case the result is just the value at `grid[0][0]`.  Otherwise, we have the following recurrence:

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


This approach has exponential time complexity due to overlapping subproblems.

```python
def minPathSum_recursive(grid):
    def solve(i, j):
        if i == 0 and j == 0:
            return grid[i][j]
        if i < 0 or j < 0:
            return float('inf')
        return grid[i][j] + min(solve(i - 1, j), solve(i, j - 1))

    return solve(len(grid) - 1, len(grid[0]) - 1)

Optimal Solution (Dynamic Programming)

A much better approach is to use dynamic programming. We can create a 2D array dp where dp[i][j] stores the minimum path sum from (0, 0) to (i, j). We can initialize dp[0][0] to grid[0][0]. Then, we can fill in the rest of the dp array using the following recurrence:

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

where dp[i-1][j] represents the minimum path sum from (0, 0) to (i-1, j) and dp[i][j-1] represents the minimum path sum from (0, 0) to (i, j-1). If either i or j is 0, we only have one option to come from. For example, if i is 0, then we can only come from (0, j-1). The final answer will be stored in dp[m-1][n-1]. This approach has O(mn) time complexity and O(mn) space complexity.

Here's the Python code:

def minPathSum(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(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]

We can further optimize the space complexity to O(n) by using only one row to store the dp values, since we only need the previous row to calculate the current row.

def minPathSum_optimized(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n

    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]

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

    return dp[n-1]

Big(O) Time Complexity 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 over each cell in the grid once to fill in the dp array.

Big(O) Space Complexity Analysis

The dynamic programming solution with the 2D dp array has a space complexity of O(m*n), as we store the minimum path sum for each cell in the grid. The optimized version with a 1D dp array has a space complexity of O(n), as we only store the minimum path sum for the current row.

Edge Cases

Empty Grid: If the grid is empty (either m or n is 0), we should return 0, or throw an exception, depending on the problem requirements.
Single Cell Grid: If the grid has only one cell (m=1, n=1), the minimum path sum is simply the value of that cell.
Negative Numbers: The problem statement specifies non-negative numbers. If negative numbers were allowed, the problem would become more complex and might require a different approach (e.g., Dijkstra's algorithm) to handle potential negative cycles.
Large Numbers: If the numbers in the grid are very large, we might need to consider using a data type that can handle larger values to avoid overflow issues.