# Minimum Falling Path Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-falling-path-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-falling-path-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Dream11](https://scaleengineer.com/companies/dream11)
---
## Problem
Given an `n x n` array of integers `matrix`, return _the **minimum sum** of any **falling path** through_ `matrix`.

A **falling path** starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position `(row, col)` will be `(row + 1, col - 1)`, `(row + 1, col)`, or `(row + 1, col + 1)`.

**Example 1:**

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

**Input:** matrix = [[2,1,3],[6,5,4],[7,8,9]]
**Output:** 13
**Explanation:** There are two falling paths with a minimum sum as shown.

**Example 2:**

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

**Input:** matrix = [[-19,57],[-40,-5]]
**Output:** -59
**Explanation:** The falling path with a minimum sum is shown.

**Constraints:**

* `n == matrix.length == matrix[i].length`
* `1 <= n <= 100`
* `-100 <= matrix[i][j] <= 100`

# Approaches
## Brute-force Recursion
This approach explores all possible falling paths starting from each cell in the first row and recursively calculates the sum for each path. The minimum sum found among all paths is the result. It's a straightforward translation of the problem definition into a recursive structure.
**Time:** O(n * 3^n). For each of the n starting cells in the first row, we explore a ternary tree of depth n, leading to an exponential number of computations. · **Space:** O(n), where n is the number of rows. This space is used by the recursion stack.
**Pros:** Simple to understand and implement as it directly follows the problem's recursive nature.
**Cons:** Extremely inefficient due to a large number of redundant calculations.; Will result in a 'Time Limit Exceeded' (TLE) error for larger values of `n` (e.g., `n > 20`).
### Explanation
We define a recursive function, let's call it `findMinPath(row, col)`, that calculates the minimum sum of a falling path starting from the cell `(row, col)`.

The base case for the recursion is when we reach the last row (`row == n-1`). In this case, the function simply returns the value of the cell `matrix[row][col]`.

For any other cell `(row, col)`, the function calculates its path sum by adding `matrix[row][col]` to the minimum of the path sums starting from the three possible next cells in the row below: `(row+1, col-1)`, `(row+1, col)`, and `(row+1, col+1)`. We must handle boundary conditions for the columns to ensure we don't go out of bounds.

The main function will call this recursive function for every cell in the first row (`(0, 0), (0, 1), ..., (0, n-1)`) and return the minimum value among these calls. This method is highly inefficient because it recomputes the minimum path sums for the same cells multiple times.

```java
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) {
            return 0;
        }
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minSum = Math.min(minSum, findMinPath(0, j, matrix));
        }
        return minSum;
    }

    private int findMinPath(int row, int col, int[][] matrix) {
        int n = matrix.length;
        // Boundary checks for columns
        if (col < 0 || col >= n) {
            return Integer.MAX_VALUE;
        }
        // Base case: last row
        if (row == n - 1) {
            return matrix[row][col];
        }

        // Recursive step
        int left = findMinPath(row + 1, col - 1, matrix);
        int middle = findMinPath(row + 1, col, matrix);
        int right = findMinPath(row + 1, col + 1, matrix);

        return matrix[row][col] + Math.min(left, Math.min(middle, right));
    }
}
```
### Algorithm
- 1. The main function initializes a variable `minSum` to `Integer.MAX_VALUE`.
- 2. It then iterates through each column `j` of the first row (from `0` to `n-1`).
- 3. For each starting cell `(0, j)`, it calls a recursive helper function, `findMinPath(0, j, matrix)`, which is designed to find the minimum falling path sum starting from that cell.
- 4. The `minSum` is updated with the minimum of its current value and the value returned by the recursive call.
- 5. The `findMinPath(row, col, matrix)` helper function works as follows:
  - a. It first checks if the column `col` is out of bounds (`< 0` or `>= n`). If so, it returns `Integer.MAX_VALUE` to ensure this path is not chosen.
  - b. It checks for the base case: if `row` is the last row (`n-1`), it returns the value of the current cell, `matrix[row][col]`, as the path ends here.
  - c. If it's not the base case, it makes three recursive calls for the cells in the next row: `(row + 1, col - 1)`, `(row + 1, col)`, and `(row + 1, col + 1)`.
  - d. It returns the sum of the current cell's value (`matrix[row][col]`) and the minimum value returned by the three recursive calls.
- 6. After the loop in the main function completes, `minSum` holds the minimum falling path sum, which is then returned.

## Recursion with Memoization (Top-Down DP)
This approach improves upon the brute-force recursion by using a memoization table (a 2D array) to store the results of subproblems that have already been solved. This is a top-down dynamic programming technique that avoids redundant computations by looking up previously computed values.
**Time:** O(n^2). Each of the `n*n` subproblems (states) is solved only once. The work for each state is constant. · **Space:** O(n^2). This is dominated by the `n x n` memoization table. The recursion stack also uses O(n) space.
**Pros:** Drastically more efficient than brute-force, with a polynomial time complexity.; Guaranteed to pass within typical time limits.; Maintains the recursive structure which can be intuitive.
**Cons:** Requires O(n^2) extra space for the memoization table, which can be substantial for large `n`.
### Explanation
We use a 2D array, `memo`, of the same dimensions as the input `matrix`, to store the minimum falling path sum starting from each cell `(row, col)`. We initialize the `memo` table with a special value (e.g., `Integer.MAX_VALUE`) to indicate that a state has not been computed yet.

The recursive function `findMinPath(row, col)` is modified:
- Before computing the result, it first checks if `memo[row][col]` already contains a computed value. If so, it returns the stored value immediately.
- If not, it computes the result recursively, just like in the brute-force approach.
- Before returning, it stores the computed result in `memo[row][col]` for future use.

This technique ensures that the minimum path sum for each cell `(row, col)` is calculated only once, drastically reducing the time complexity.

```java
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) {
            return 0;
        }
        int[][] memo = new int[n][n];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        }

        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minSum = Math.min(minSum, findMinPath(0, j, matrix, memo));
        }
        return minSum;
    }

    private int findMinPath(int row, int col, int[][] matrix, int[][] memo) {
        int n = matrix.length;
        if (col < 0 || col >= n) {
            return Integer.MAX_VALUE;
        }
        if (row == n - 1) {
            return matrix[row][col];
        }
        if (memo[row][col] != Integer.MAX_VALUE) {
            return memo[row][col];
        }

        int left = findMinPath(row + 1, col - 1, matrix, memo);
        int middle = findMinPath(row + 1, col, matrix, memo);
        int right = findMinPath(row + 1, col + 1, matrix, memo);

        memo[row][col] = matrix[row][col] + Math.min(left, Math.min(middle, right));
        return memo[row][col];
    }
}
```
### Algorithm
- 1. Create a memoization table, `memo`, of the same size as the input `matrix` and initialize all its cells with a sentinel value (e.g., `Integer.MAX_VALUE`) to indicate that they haven't been computed.
- 2. The main function iterates through each starting column `j` in the first row.
- 3. It calls a helper recursive function `findMinPath(0, j, matrix, memo)` and keeps track of the minimum sum found.
- 4. The `findMinPath(row, col, matrix, memo)` function is modified from the brute-force version:
  - a. It first checks if the result for `(row, col)` is already stored in `memo[row][col]`. If `memo[row][col]` is not the sentinel value, it returns the stored result immediately.
  - b. If the result is not memoized, it proceeds with the same logic as the brute-force approach: handle boundaries, check for the base case (last row), and make recursive calls for the three children cells.
  - c. After computing the result, it stores it in `memo[row][col]` before returning it.
- 5. The final result is the minimum value found after checking all starting positions in the first row.

## Tabulation (Bottom-Up DP)
This approach uses an iterative, bottom-up method to solve the problem. It builds the solution from the base cases (the first row) upwards. A 2D DP table is used to store the minimum falling path sum ending at each cell, effectively eliminating recursion.
**Time:** O(n^2) due to the nested loops iterating through the entire matrix once. · **Space:** O(n^2) for the `dp` table.
**Pros:** Avoids recursion and potential stack overflow issues for very deep recursion.; Often slightly faster in practice than memoization due to the absence of recursion overhead.; The iterative logic can be easier to reason about for some.
**Cons:** Uses O(n^2) extra space, which is the same as memoization and can be improved.
### Explanation
We create a 2D array `dp` of the same size as the `matrix`. `dp[i][j]` will store the minimum sum of a falling path that ends at cell `(i, j)`.

The base case is the first row. We initialize the first row of our `dp` table with the values from the first row of the `matrix`: `dp[0][j] = matrix[0][j]`.

We then iterate from the second row (`i = 1`) to the last row (`i = n-1`). For each cell `(i, j)`, we calculate `dp[i][j]` based on the values in the previous row of the `dp` table. The recurrence relation is: `dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])`.

After filling the entire `dp` table, the values in the last row `dp[n-1]` represent the total minimum sums of all falling paths ending at each respective column. The final answer is the minimum value in this last row.

```java
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[n][n];

        // Initialize the first row of dp table
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j];
        }

        // Fill the rest of the dp table
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int middle = dp[i - 1][j];
                int left = (j > 0) ? dp[i - 1][j - 1] : Integer.MAX_VALUE;
                int right = (j < n - 1) ? dp[i - 1][j + 1] : Integer.MAX_VALUE;
                dp[i][j] = matrix[i][j] + Math.min(middle, Math.min(left, right));
            }
        }

        // Find the minimum sum in the last row
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minSum = Math.min(minSum, dp[n - 1][j]);
        }
        return minSum;
    }
}
```
### Algorithm
- 1. Create a 2D DP table, `dp`, of size `n x n`.
- 2. Initialize the first row of the `dp` table by copying the values from the first row of the input `matrix`. This is our base case: `dp[0][j] = matrix[0][j]`.
- 3. Iterate through the matrix row by row, starting from the second row (`i = 1` to `n-1`).
- 4. For each cell `(i, j)` in the current row, calculate its DP value using the recurrence relation: `dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])`.
- 5. Handle boundary conditions for columns. For `j=0`, the 'left' option is not available. For `j=n-1`, the 'right' option is not available. Use a large value like `Integer.MAX_VALUE` for out-of-bounds predecessors.
- 6. After filling the entire `dp` table, the last row `dp[n-1]` will contain the minimum falling path sums ending at each column `j`.
- 7. Find the minimum value in the last row of the `dp` table and return it as the final answer.

## Space-Optimized Bottom-Up DP
This approach optimizes the space complexity of the tabulation method. By observing that the calculation for the current row's DP values only depends on the values from the immediately preceding row, we can avoid storing the entire 2D DP table. Instead, we only need to keep track of the previous row's results, reducing the space requirement significantly.
**Time:** O(n^2). The nested loop structure remains the same as the standard tabulation approach. · **Space:** O(n). We use two 1D arrays of size `n` to store the DP values for the previous and current rows.
**Pros:** Significant space improvement over the standard tabulation and memoization approaches.; Maintains the efficient O(n^2) time complexity.
**Cons:** Slightly more complex logic to manage two arrays compared to a single 2D DP table.
### Explanation
Instead of a full `n x n` DP table, we only need to store the DP values for the previous row to compute the current row. We can use a 1D array, let's call it `prevRow`, of size `n`.

We initialize `prevRow` with the values from the first row of the `matrix`. Then, we iterate from the second row (`i = 1`) to the last row (`i = n-1`). In each iteration, we compute a `currRow` (another 1D array of size `n`) using the values from `prevRow`. After computing all values for `currRow`, we update `prevRow` to be `currRow` for the next iteration.

After the outer loop finishes, `prevRow` will hold the minimum path sums for the last row. The final answer is the minimum value in this `prevRow` array.

```java
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) {
            return 0;
        }

        int[] prevRow = new int[n];
        // Initialize prevRow with the first row of the matrix
        System.arraycopy(matrix[0], 0, prevRow, 0, n);

        for (int i = 1; i < n; i++) {
            int[] currRow = new int[n];
            for (int j = 0; j < n; j++) {
                int middle = prevRow[j];
                int left = (j > 0) ? prevRow[j - 1] : Integer.MAX_VALUE;
                int right = (j < n - 1) ? prevRow[j + 1] : Integer.MAX_VALUE;
                currRow[j] = matrix[i][j] + Math.min(middle, Math.min(left, right));
            }
            // Update prevRow for the next iteration
            prevRow = currRow;
        }

        // Find the minimum sum in the last row's dp values
        int minSum = Integer.MAX_VALUE;
        for (int val : prevRow) {
            minSum = Math.min(minSum, val);
        }
        return minSum;
    }
}
```
### Algorithm
- 1. Create a 1D array, `prevRow`, of size `n`.
- 2. Initialize `prevRow` with the values from the first row of the `matrix`.
- 3. Iterate from the second row of the matrix (`i = 1` to `n-1`).
- 4. Inside this loop, create another 1D array, `currRow`, of size `n`.
- 5. Iterate through the columns (`j = 0` to `n-1`) of the current row `i`.
- 6. For each column `j`, calculate `currRow[j]` using the values from `prevRow`: `currRow[j] = matrix[i][j] + min(prevRow[j-1], prevRow[j], prevRow[j+1])`, handling column boundaries.
- 7. After the inner loop (all columns of row `i` are processed), update `prevRow` to be `currRow` for the next iteration (i.e., `prevRow = currRow`).
- 8. After the outer loop finishes, `prevRow` will hold the minimum path sums for the last row.
- 9. Find and return the minimum value in the `prevRow` array.

## In-place Space-Optimized DP
This is the most space-efficient approach. It builds upon the bottom-up DP logic but cleverly reuses the input matrix itself as the DP table. This eliminates the need for any extra space proportional to the input size, achieving constant extra space complexity.
**Time:** O(n^2). We traverse the matrix once to update the values. · **Space:** O(1). No extra space proportional to the input size is used. We only use a few variables for loops and storing temporary values.
**Pros:** Optimal space complexity.; Very efficient in both time and space.; Code is concise and clean.
**Cons:** This approach modifies the input matrix, which might be undesirable if the original matrix needs to be preserved.
### Explanation
This approach modifies the input `matrix` in-place to store the DP values. This is possible because when we compute the values for row `i`, we only need the values from row `i-1`. Once `matrix[i][j]` is updated, its original value is no longer needed for any subsequent calculations in this problem.

We start our iteration from the second row (`i = 1`). For each cell `(i, j)`, we update its value by adding the minimum of the path sums from the cells above it in the previous row. The previous row `i-1` already contains the computed minimum path sums up to that row.

The update rule is: `matrix[i][j] = matrix[i][j] + min(matrix[i-1][j-1], matrix[i-1][j], matrix[i-1][j+1])`, with boundary checks. After iterating through all rows, the last row of the `matrix` will contain the final minimum sums. The answer is the minimum value in this modified last row.

```java
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) {
            return 0;
        }

        // Iterate from the second row, updating the matrix in-place
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Get the minimum from the previous row
                int middle = matrix[i - 1][j];
                int left = (j > 0) ? matrix[i - 1][j - 1] : Integer.MAX_VALUE;
                int right = (j < n - 1) ? matrix[i - 1][j + 1] : Integer.MAX_VALUE;
                
                // Update the current cell with the minimum path sum
                matrix[i][j] += Math.min(middle, Math.min(left, right));
            }
        }

        // Find the minimum in the last row of the modified matrix
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minSum = Math.min(minSum, matrix[n - 1][j]);
        }
        return minSum;
    }
}
```
### Algorithm
- 1. Start iterating from the second row of the matrix (`i = 1` to `n-1`).
- 2. For each row `i`, iterate through its columns (`j = 0` to `n-1`).
- 3. For each cell `(i, j)`, find the minimum path sum from the three possible parent cells in the previous row `i-1`: `matrix[i-1][j-1]`, `matrix[i-1][j]`, and `matrix[i-1][j+1]`. Handle boundary conditions for `j-1` and `j+1`.
- 4. Update the value of the current cell `matrix[i][j]` by adding this minimum value to it. `matrix[i][j] += min_from_previous_row`.
- 5. After the loops complete, the last row of the matrix (`matrix[n-1]`) will have been updated to contain the minimum falling path sums ending at each respective cell.
- 6. Iterate through the last row of the modified matrix to find the minimum value.
- 7. Return this minimum value as the final answer.

# Solutions
### Java

```java
class Solution {
public
  int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    var f = new int[n];
    for (var row : matrix) {
      var g = f.clone();
      for (int j = 0; j < n; ++j) {
        if (j > 0) {
          g[j] = Math.min(g[j], f[j - 1]);
        }
        if (j + 1 < n) {
          g[j] = Math.min(g[j], f[j + 1]);
        }
        g[j] += row[j];
      }
      f = g;
    }
```

### CPP

```cpp
class Solution {
public:
  int minFallingPathSum(vector<vector<int>> &matrix) {
    int n = matrix.size();
    vector<int> f(n);
    for (auto &row : matrix) {
      auto g = f;
      for (int j = 0; j < n; ++j) {
        if (j) {
          g[j] = min(g[j], f[j - 1]);
        }
        if (j + 1 < n) {
          g[j] = min(g[j], f[j + 1]);
        }
        g[j] += row[j];
      }
      f = move(g);
    }
    return *min_element(f.begin(), f.end());
  }
};

```

### Python

```python
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int: n = len(matrix) f = [0] * n for row in matrix: g = [0] * n for j, x in enumerate(row): l, r = max(0, j - 1), min(n, j + 2) g[j] = min(f[l: r]) + x f = g return min(f)

```