# Minimum Path Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-path-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-path-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [eBay](https://scaleengineer.com/companies/ebay), [Salesforce](https://scaleengineer.com/companies/salesforce), [Dream11](https://scaleengineer.com/companies/dream11), [General Motors](https://scaleengineer.com/companies/general-motors)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-path-sum/image0.jpg) 

**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.

**Example 2:**

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

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 200`
* `0 <= grid[i][j] <= 200`

# Approaches
## Brute Force Recursion
The most intuitive approach is to try every possible path from the top-left to the bottom-right corner. Since we can only move right or down, we can use recursion to explore both moves from any given cell. We then find the path that results in the minimum sum.
**Time:** O(2^(m+n)) · **Space:** O(m + n)
**Pros:** Simple to conceptualize and implement.; Follows the problem's constraints (down or right moves) directly.
**Cons:** Extremely inefficient due to a large number of redundant calculations for the same subproblems.; Will result in a 'Time Limit Exceeded' error for all but the smallest grids.
### Explanation
We can define a recursive function, say `calculate(grid, i, j)`, that computes the minimum path sum from the cell `(i, j)` to the destination at `(m-1, n-1)`.

For any cell `(i, j)`, the path can continue either down to `(i+1, j)` or right to `(i, j+1)`. Therefore, the minimum path sum from `(i, j)` is its own value `grid[i][j]` plus the minimum of the path sums starting from these two adjacent cells.

The base case for the recursion is the destination cell `(m-1, n-1)`. The minimum path from the destination to itself is just its own value. If a recursive call goes out of the grid's boundaries, it represents an invalid path, so we return a value equivalent to infinity to ensure it's never chosen as the minimum.

This method explores all possible paths, but because many paths will cross over the same cells, it ends up re-calculating the minimum path sum from those cells multiple times.

```java
class Solution {
    public int minPathSum(int[][] grid) {
        return calculate(grid, 0, 0);
    }

    private int calculate(int[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;

        if (i >= m || j >= n) {
            return Integer.MAX_VALUE;
        }

        if (i == m - 1 && j == n - 1) {
            return grid[i][j];
        }

        // To avoid integer overflow when adding grid[i][j], we find the min first.
        int minOfNextSteps = Math.min(calculate(grid, i + 1, j), calculate(grid, i, j + 1));

        return grid[i][j] + minOfNextSteps;
    }
}
```
### Algorithm
*   Define a recursive function `calculate(grid, i, j)`.
*   **Base Case:** If `i` or `j` are out of bounds, return a very large number (infinity) to signify an invalid path.
*   **Base Case:** If `(i, j)` is the bottom-right corner `(m-1, n-1)`, return `grid[i][j]`.
*   **Recursive Step:** Recursively call the function for the cell below `(i+1, j)` and the cell to the right `(i, j+1)`.
*   Return `grid[i][j] + min(result_from_down, result_from_right)`.
*   The initial call is `calculate(grid, 0, 0)`.

## Dynamic Programming with Memoization
The brute-force approach is slow because it re-computes the minimum path sum for the same cells multiple times. We can significantly improve performance by caching the results of these subproblems. This technique, where we use a recursive structure but store results to avoid re-computation, is known as memoization or top-down dynamic programming.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Drastically improves time complexity by eliminating redundant computations.; Guarantees that each subproblem is solved only once.
**Cons:** Requires extra space for the memoization table, which is O(m*n).; Can still lead to a stack overflow error on very large grids due to deep recursion, although the constraints (m, n <= 200) make this less likely.
### Explanation
We introduce a 2D array, `memo`, with the same dimensions as the input `grid`. This `memo` table will store the results of our `calculate(i, j)` function. Each cell `memo[i][j]` is initialized to a value that indicates it hasn't been computed yet (e.g., -1).

Inside the recursive function, before performing any calculations for cell `(i, j)`, we first check if `memo[i][j]` contains a valid pre-computed result. If it does, we return it immediately. Otherwise, we perform the calculation as in the brute-force approach. Once the result is computed, we store it in `memo[i][j]` before returning. This ensures that the minimum path sum for each cell is calculated exactly once.

```java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] memo = new int[m][n];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return calculate(grid, 0, 0, memo);
    }

    private int calculate(int[][] grid, int i, int j, int[][] memo) {
        int m = grid.length;
        int n = grid[0].length;

        if (i >= m || j >= n) {
            return Integer.MAX_VALUE;
        }

        if (i == m - 1 && j == n - 1) {
            return grid[i][j];
        }

        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int minOfNextSteps = Math.min(calculate(grid, i + 1, j, memo), calculate(grid, i, j + 1, memo));

        memo[i][j] = grid[i][j] + minOfNextSteps;
        return memo[i][j];
    }
}
```
### Algorithm
*   Create a 2D `memo` array of the same size as `grid`, initialized with a sentinel value (e.g., -1).
*   Define a recursive function `calculate(grid, i, j, memo)`.
*   Handle base cases for out-of-bounds and destination cell as in the brute-force approach.
*   Before computing, check if `memo[i][j]` is already computed. If so, return the stored value.
*   If not, recursively compute the minimum sum from the 'down' and 'right' paths.
*   Store the result in `memo[i][j]` before returning: `memo[i][j] = grid[i][j] + min(down, right)`.

## 2D Dynamic Programming (Bottom-Up)
We can also solve this problem iteratively using a bottom-up approach. We build the solution from the start `(0,0)` towards the end `(m-1, n-1)`. We use a 2D DP table where `dp[i][j]` stores the minimum path sum to reach cell `(i,j)`.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Efficient with a polynomial time complexity.; Avoids recursion, which can prevent stack overflow issues and may have slightly better performance due to lower overhead.
**Cons:** Requires O(m*n) extra space for the DP table, same as the memoization approach.
### Explanation
We create a 2D array `dp` of the same size as the `grid`. The value `dp[i][j]` will represent the minimum sum of a path from the top-left corner `(0,0)` to the cell `(i,j)`.

The state transition is based on the fact that to reach cell `(i,j)`, we must have come from either the cell above, `(i-1,j)`, or the cell to the left, `(i,j-1)`. Therefore, the minimum path sum to `(i,j)` is `grid[i][j]` plus the minimum of the path sums to its top and left neighbors.

We fill the `dp` table by first initializing the base cases (the first row and first column) and then iterating through the rest of the cells, applying the transition formula. The final answer is the value in the bottom-right corner of the `dp` table.

```java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

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

        // Initialize first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // Initialize first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // Fill the rest of the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m - 1][n - 1];
    }
}
```
### Algorithm
*   Create a 2D `dp` array of size `m x n`.
*   `dp[i][j]` will store the minimum path sum from `(0,0)` to `(i,j)`.
*   Initialize the top-left cell: `dp[0][0] = grid[0][0]`.
*   Fill the first row: `dp[0][j] = dp[0][j-1] + grid[0][j]`.
*   Fill the first column: `dp[i][0] = dp[i-1][0] + grid[i][0]`.
*   Iterate through the rest of the grid from `(1,1)` to `(m-1,n-1)` and fill `dp[i][j]` using the relation: `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`.
*   The final answer is `dp[m-1][n-1]`.

## 1D Dynamic Programming (Space Optimized)
Observing the 2D DP recurrence relation, `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`, we can see that to compute the values for the current row `i`, we only need the values from the previous row `i-1`. This insight allows us to optimize the space complexity by using a 1D array instead of a 2D table.
**Time:** O(m * n) · **Space:** O(n)
**Pros:** Highly space-efficient, reducing space from O(m*n) to O(n) or O(min(m,n)).; Maintains the optimal time complexity of O(m*n).
**Cons:** The logic can be slightly more complex to reason about compared to the 2D DP approach.
### Explanation
Instead of a 2D `dp` table, we use a 1D array, `dp`, of size `n`. This `dp` array will store the minimum path sums for the cells in the current row being processed.

We start by initializing the `dp` array with the path sums for the first row. Then, we iterate through the remaining rows of the grid one by one. For each new row `i`, we update the `dp` array. The new `dp[j]` (for row `i`) is calculated using the old `dp[j]` (which represents the value from row `i-1`) and the new `dp[j-1]` (which represents the value from the current row `i` at the previous column).

The update for `dp[0]` is special as it can only come from above. For other `dp[j]`, it's the minimum of the value from above (the old `dp[j]`) and the value from the left (the new `dp[j-1]`), plus the grid value. After processing all rows, `dp[n-1]` will hold the final answer.

```java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];

        // Initialize dp array with the first row's path sums
        dp[0] = grid[0][0];
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }

        // Iterate over the rest of the rows
        for (int i = 1; i < m; i++) {
            // Update the first column's path sum for the current row
            dp[0] = dp[0] + grid[i][0];
            // Update the rest of the columns for the current row
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
*   Create a 1D `dp` array of size `n` (number of columns).
*   Initialize the `dp` array by computing the path sums for the first row of the grid.
*   Iterate from the second row (`i=1`) to the last row (`m-1`):
    *   Update the first element `dp[0]` for the current row: `dp[0] = dp[0] + grid[i][0]`.
    *   Iterate from the second column (`j=1`) to the last column (`n-1`):
    *   Update `dp[j]` using the formula: `dp[j] = min(dp[j], dp[j-1]) + grid[i][j]`.
*   The final answer is `dp[n-1]`.

## In-place Dynamic Programming
This is the most space-efficient dynamic programming solution. We can eliminate the need for any extra space (besides a few variables) by using the input `grid` itself as our DP table. The original value of `grid[i][j]` is only needed once to compute the cumulative path sum to that cell, so we can overwrite it with the result.
**Time:** O(m * n) · **Space:** O(1)
**Pros:** Optimal space complexity, as no extra space proportional to the input size is used.; Very efficient in both time and space.
**Cons:** This approach modifies the input grid, which might be undesirable if the original grid needs to be preserved.
### Explanation
The logic is identical to the 2D bottom-up DP approach, but all updates are performed directly on the input `grid`. `grid[i][j]` is repurposed to store the minimum path sum from `(0,0)` to `(i,j)`.

We first pre-process the first row and first column, as their minimum path sums are straightforward to calculate (they can only be reached from one direction). Then, we iterate through the rest of the grid, updating each `grid[i][j]` by adding its original value to the minimum of the already-updated values in the cell above (`grid[i-1][j]`) and to the left (`grid[i][j-1]`).

After the loops complete, the entire grid is filled with cumulative path sums, and the value at `grid[m-1][n-1]` is our final answer.

```java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Update first row
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        // Update first column
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        // Update the rest of the grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
}
```
### Algorithm
*   Use the input `grid` itself as the DP table.
*   Update the first row: `grid[0][j] = grid[0][j] + grid[0][j-1]` for `j` from 1 to `n-1`.
*   Update the first column: `grid[i][0] = grid[i][0] + grid[i-1][0]` for `i` from 1 to `m-1`.
*   Iterate through the rest of the grid from `(1,1)`.
*   Update each cell with the formula: `grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1])`.
*   Return the value at the bottom-right corner, `grid[m-1][n-1]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[, ] f = new int[m, n];
        f[0, 0] = grid[0][0];
        for (int i = 1; i < m; ++i) {
            f[i, 0] = f[i - 1, 0] + grid[i][0];
        }
        for (int j = 1; j < n; ++j) {
            f[0, j] = f[0, j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i, j] = Math.Min(f[i - 1, j], f[i, j - 1]) + grid[i][j];
            }
        }
        return f[m - 1, n - 1];
    }
}
```

### Java

```java
class Solution {
public
  int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] f = new int[m][n];
    f[0][0] = grid[0][0];
    for (int i = 1; i < m; ++i) {
      f[i][0] = f[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < n; ++j) {
      f[0][j] = f[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
      }
    }
    return f[m - 1][n - 1];
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var minPathSum = function (
  grid,
) {
  const m = grid.length;
  const n = grid[0].length;
  const f = Array(m)
    .fill(0)
    .map(() => Array(n).fill(0));
  f[0][0] = grid[0][0];
  for (let i = 1; i < m; ++i) {
    f[i][0] = f[i - 1][0] + grid[i][0];
  }
  for (let j = 1; j < n; ++j) {
    f[0][j] = f[0][j - 1] + grid[0][j];
  }
  for (let i = 1; i < m; ++i) {
    for (let j = 1; j < n; ++j) {
      f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
    }
  }
  return f[m - 1][n - 1];
};

```

### CPP

```cpp
class Solution {
public:
  int minPathSum(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int f[m][n];
    f[0][0] = grid[0][0];
    for (int i = 1; i < m; ++i) {
      f[i][0] = f[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < n; ++j) {
      f[0][j] = f[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
      }
    }
    return f[m - 1][n - 1];
  }
};

```

### Python

```python
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[0] * n for _ in range(m)] f[0][0] = grid[0][0] for i in range(1, m): f[i][0] = f[i - 1][0] + grid[i][0] for j in range(1, n): f[0][j] = f[0][j - 1] + grid[0][j] for i in range(1, m): for j in range(1, n): f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j] return f[- 1][- 1]

```