# Minimum Falling Path Sum II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-falling-path-sum-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-falling-path-sum-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox)
---
## Problem
Given an `n x n` integer matrix `grid`, return _the minimum sum of a **falling path with non-zero shifts**_.

A **falling path with non-zero shifts** is a choice of exactly one element from each row of `grid` such that no two elements chosen in adjacent rows are in the same column.

**Example 1:**

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

**Input:** grid = [[1,2,3],[4,5,6],[7,8,9]]
**Output:** 13
**Explanation:** 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

**Example 2:**

**Input:** grid = [[7]]
**Output:** 7

**Constraints:**

* `n == grid.length == grid[i].length`
* `1 <= n <= 200`
* `-99 <= grid[i][j] <= 99`

# Approaches
## Standard Dynamic Programming (Bottom-Up)
This approach uses a 2D dynamic programming table to solve the problem. Let `dp[i][j]` represent the minimum sum of a falling path ending at the cell `(i, j)`. We build this table row by row, from top to bottom.
**Time:** O(n^3). We have three nested loops. The outer two iterate through each cell of the grid (`n*n`), and for each cell, the inner loop iterates through the `n` columns of the previous row. · **Space:** O(n^2). We use an additional `dp` table of size `n x n`.
**Pros:** Conceptually straightforward and easy to understand.; Correctly solves the problem by exploring all valid paths systematically.
**Cons:** Inefficient due to the nested loop structure.; High time complexity makes it slow for larger grids, potentially leading to a 'Time Limit Exceeded' error on online judges.
### Explanation
The core idea is to define a recurrence relation. The minimum path sum to reach `grid[i][j]` is `grid[i][j]` plus the minimum path sum of the previous row `i-1`, with the constraint that we cannot come from the same column `j`.

So, `dp[i][j] = grid[i][j] + min(dp[i-1][k])` for all `k` where `k != j`.

We initialize a `dp` table of the same size as the `grid`. The first row of `dp` is the same as the first row of `grid`, as there's no path before it.

Then, we iterate from the second row to the last. For each cell `(i, j)`, we calculate `dp[i][j]` by finding the minimum value in the previous row `dp[i-1]` excluding the element at column `j`, and adding it to `grid[i][j]`.

After filling the entire `dp` table, the minimum value in the last row `dp[n-1]` will be the overall minimum falling path sum.

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

        int[][] dp = new int[n][n];

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

        // Fill the rest of the dp table
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int minPrevRow = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    if (k != j) {
                        minPrevRow = Math.min(minPrevRow, dp[i - 1][k]);
                    }
                }
                dp[i][j] = grid[i][j] + minPrevRow;
            }
        }

        // 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. Get the dimension `n` of the `grid`. If `n` is 1, return `grid[0][0]`.
2. Create a 2D DP array `dp` of size `n x n`.
3. Initialize the first row of `dp` with the values from the first row of `grid`: `dp[0][j] = grid[0][j]` for `j` from `0` to `n-1`.
4. Iterate through the rows from `i = 1` to `n-1`.
5. For each row `i`, iterate through the columns `j = 0` to `n-1`.
6. Inside this loop, find the minimum value in the previous row `dp[i-1]` excluding `dp[i-1][j]`.
   - Initialize `minPrevRow = Integer.MAX_VALUE`.
   - Iterate `k` from `0` to `n-1`.
   - If `k != j`, update `minPrevRow = min(minPrevRow, dp[i-1][k])`.
7. Calculate `dp[i][j] = grid[i][j] + minPrevRow`.
8. After filling the `dp` table, find the minimum value in the last row `dp[n-1]`.
9. Return this minimum value.

## Optimized Dynamic Programming
This approach improves upon the standard DP by optimizing the calculation for each state. Instead of re-calculating the minimum of the previous row for each cell, we can pre-calculate the two smallest values of the previous row. This reduces the time complexity significantly.
**Time:** O(n^2). The outer loop runs `n` times. Inside, we have two separate loops that each run `n` times (one to find min1/min2, one to fill the current DP row). So, `O(n * (n + n)) = O(n^2)`. · **Space:** O(n^2). We use an additional `dp` table of size `n x n`.
**Pros:** Much more efficient than the standard DP approach.; Reduces the time complexity from cubic to quadratic.
**Cons:** Still requires significant extra space for the DP table.
### Explanation
The key observation is that for any cell `(i, j)`, the minimum path sum from the previous row `i-1` will either be the absolute minimum of that row (`min1`) or the second minimum (`min2`).

- If the current column `j` is different from the column of the previous row's minimum (`min1_idx`), we can use `min1`.
- If the current column `j` is the same as `min1_idx`, we are forced to take the second best option from the previous row, which is `min2`.

So, for each row `i`, we first find the two smallest values (`min1`, `min2`) and the index of `min1` from the previous row `dp[i-1]`. This can be done in a single pass `O(n)`. Then, we iterate through the columns `j` of the current row `i` and calculate `dp[i][j]` in `O(1)` time using `min1` and `min2`.

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

        int[][] dp = new int[n][n];
        System.arraycopy(grid[0], 0, dp[0], 0, n);

        for (int i = 1; i < n; i++) {
            // Find the two smallest values in the previous row (dp[i-1])
            int min1 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            int min1_idx = -1;

            for (int j = 0; j < n; j++) {
                if (dp[i - 1][j] < min1) {
                    min2 = min1;
                    min1 = dp[i - 1][j];
                    min1_idx = j;
                } else if (dp[i - 1][j] < min2) {
                    min2 = dp[i - 1][j];
                }
            }

            // Fill the current row of dp table
            for (int j = 0; j < n; j++) {
                if (j == min1_idx) {
                    dp[i][j] = grid[i][j] + min2;
                } else {
                    dp[i][j] = grid[i][j] + min1;
                }
            }
        }

        int result = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            result = Math.min(result, dp[n - 1][j]);
        }

        return result;
    }
}
```
### Algorithm
1. Get the dimension `n` of the `grid`. If `n` is 1, return `grid[0][0]`.
2. Create a 2D DP array `dp` of size `n x n`.
3. Initialize the first row of `dp` with the values from the first row of `grid`.
4. Iterate through the rows from `i = 1` to `n-1`.
5. In each iteration `i`, find the two smallest values (`min1`, `min2`) and the index of the smallest value (`min1_idx`) in the previous row `dp[i-1]`.
   - Initialize `min1 = Integer.MAX_VALUE`, `min2 = Integer.MAX_VALUE`, `min1_idx = -1`.
   - Iterate `k` from `0` to `n-1` over `dp[i-1]`.
   - If `dp[i-1][k]` is smaller than `min1`, update `min2 = min1`, `min1 = dp[i-1][k]`, and `min1_idx = k`.
   - Else if `dp[i-1][k]` is smaller than `min2`, update `min2 = dp[i-1][k]`.
6. For each column `j` in the current row `i`:
   - If `j == min1_idx`, `dp[i][j] = grid[i][j] + min2`.
   - Otherwise, `dp[i][j] = grid[i][j] + min1`.
7. After filling the `dp` table, find the minimum value in the last row `dp[n-1]`.
8. Return this minimum value.

## Space-Optimized Dynamic Programming
This is the most efficient approach. It builds upon the optimized DP logic but reduces the space complexity. Since the calculation for the current row only depends on the values from the immediately preceding row, we don't need to store the entire DP table. We can modify the input grid in-place to achieve constant extra space.
**Time:** O(n^2). The complexity remains the same as the previous optimized approach. We iterate through the grid once. · **Space:** O(1). We modify the grid in-place and only use a few variables to store the minimums, resulting in constant extra space. If an auxiliary array is used instead of modifying the input, the space complexity would be `O(n)`.
**Pros:** Optimal time complexity for this problem.; Optimal space complexity, as it uses constant extra space (by modifying the input).
**Cons:** Modifies the input array, which might not be desirable in all contexts. If modification is disallowed, an `O(n)` space solution using an auxiliary array for the previous row is a simple alternative.
### Explanation
The logic is identical to the optimized `O(n^2)` DP approach. The only difference is in the implementation of space usage. Instead of a full `dp` table, we can modify the input `grid` itself to store the DP values. `grid[i][j]` will be updated to store the minimum falling path sum ending at that cell. This is possible because once we compute row `i`, the original values of `grid[i-1]` are no longer needed for subsequent calculations.

We iterate from the second row. For each row, we find the two minimums from the *updated* previous row. Then we update the current row's values by adding the appropriate minimum.

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

        for (int i = 1; i < n; i++) {
            // Find the two smallest values in the previous row
            int min1 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            int min1_idx = -1;

            for (int j = 0; j < n; j++) {
                if (grid[i - 1][j] < min1) {
                    min2 = min1;
                    min1 = grid[i - 1][j];
                    min1_idx = j;
                } else if (grid[i - 1][j] < min2) {
                    min2 = grid[i - 1][j];
                }
            }

            // Update the current row with the new path sums
            for (int j = 0; j < n; j++) {
                if (j == min1_idx) {
                    grid[i][j] += min2;
                } else {
                    grid[i][j] += min1;
                }
            }
        }

        // Find the minimum in the last row
        int result = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            result = Math.min(result, grid[n - 1][j]);
        }

        return result;
    }
}
```
### Algorithm
1. Get the dimension `n` of the `grid`. If `n` is 1, return `grid[0][0]`.
2. Iterate through the rows of the `grid` from `i = 1` to `n-1`.
3. In each iteration `i`, find the two smallest values (`min1`, `min2`) and the index of the smallest value (`min1_idx`) in the previous row `grid[i-1]`.
4. For each column `j` in the current row `i`:
   - If `j == min1_idx`, update `grid[i][j] = grid[i][j] + min2`.
   - Otherwise, update `grid[i][j] = grid[i][j] + min1`.
5. After the loops complete, the last row of the `grid` contains the total sums for all falling paths ending at each column.
6. Find the minimum value in the last row `grid[n-1]` and return it.

# Solutions
### Java

```java
class Solution {
public
  int minFallingPathSum(int[][] grid) {
    int n = grid.length;
    int[][] f = new int[n + 1][n];
    final int inf = 1 << 30;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < n; ++j) {
        int x = inf;
        for (int k = 0; k < n; ++k) {
          if (k != j) {
            x = Math.min(x, f[i - 1][k]);
          }
        }
        f[i][j] = grid[i - 1][j] + (x == inf ? 0 : x);
      }
    }
    int ans = inf;
    for (int x : f[n]) {
      ans = Math.min(ans, x);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minFallingPathSum(vector<vector<int>> &grid) {
    int n = grid.size();
    int f[n + 1][n];
    memset(f, 0, sizeof(f));
    const int inf = 1 << 30;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < n; ++j) {
        int x = inf;
        for (int k = 0; k < n; ++k) {
          if (k != j) {
            x = min(x, f[i - 1][k]);
          }
        }
        f[i][j] = grid[i - 1][j] + (x == inf ? 0 : x);
      }
    }
    return *min_element(f[n], f[n] + n);
  }
};

```

### Python

```python
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int: n = len(grid) f = [[0] * n for _ in range(n + 1)] for i, row in enumerate(grid, 1): for j, v in enumerate(row): x = min((f[i - 1][k] for k in range(n) if k != j), default=0) f[i][j] = v + x return min(f[n])

```