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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2

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

Constraints

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

Solution

Method 1 – Dynamic Programming with Min Tracking

Intuition

To avoid picking the same column in adjacent rows, for each cell, we add the minimum value from the previous row except the same column. To optimize, we track the smallest and second smallest values in the previous row and their column indices.

Approach

  1. For each row, keep track of the minimum and second minimum values and their column indices from the previous row.
  2. For each cell in the current row:
    • If its column is not the same as the minimum column from the previous row, add the minimum value.
    • Otherwise, add the second minimum value.
  3. Update the minimums for the current row.
  4. The answer is the minimum value in the last row.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> dp = grid[0];
        for (int i = 1; i < n; ++i) {
            int min1 = INT_MAX, min2 = INT_MAX, idx1 = -1;
            for (int j = 0; j < n; ++j) {
                if (dp[j] < min1) {
                    min2 = min1; min1 = dp[j]; idx1 = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j];
                }
            }
            vector<int> ndp(n);
            for (int j = 0; j < n; ++j) {
                ndp[j] = grid[i][j] + (j == idx1 ? min2 : min1);
            }
            dp = ndp;
        }
        return *min_element(dp.begin(), dp.end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func minFallingPathSum(grid [][]int) int {
    n := len(grid)
    dp := make([]int, n)
    copy(dp, grid[0])
    for i := 1; i < n; i++ {
        min1, min2, idx1 := 1<<31-1, 1<<31-1, -1
        for j := 0; j < n; j++ {
            if dp[j] < min1 {
                min2 = min1; min1 = dp[j]; idx1 = j
            } else if dp[j] < min2 {
                min2 = dp[j]
            }
        }
        ndp := make([]int, n)
        for j := 0; j < n; j++ {
            if j == idx1 {
                ndp[j] = grid[i][j] + min2
            } else {
                ndp[j] = grid[i][j] + min1
            }
        }
        dp = ndp
    }
    ans := dp[0]
    for _, v := range dp {
        if v < ans {
            ans = v
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[] dp = grid[0].clone();
        for (int i = 1; i < n; ++i) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, idx1 = -1;
            for (int j = 0; j < n; ++j) {
                if (dp[j] < min1) {
                    min2 = min1; min1 = dp[j]; idx1 = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j];
                }
            }
            int[] ndp = new int[n];
            for (int j = 0; j < n; ++j) {
                ndp[j] = grid[i][j] + (j == idx1 ? min2 : min1);
            }
            dp = ndp;
        }
        int ans = dp[0];
        for (int v : dp) ans = Math.min(ans, v);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun minFallingPathSum(grid: Array<IntArray>): Int {
        val n = grid.size
        var dp = grid[0].clone()
        for (i in 1 until n) {
            var min1 = Int.MAX_VALUE
            var min2 = Int.MAX_VALUE
            var idx1 = -1
            for (j in 0 until n) {
                if (dp[j] < min1) {
                    min2 = min1; min1 = dp[j]; idx1 = j
                } else if (dp[j] < min2) {
                    min2 = dp[j]
                }
            }
            val ndp = IntArray(n)
            for (j in 0 until n) {
                ndp[j] = grid[i][j] + if (j == idx1) min2 else min1
            }
            dp = ndp
        }
        return dp.minOrNull() ?: 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minFallingPathSum(self, grid: list[list[int]]) -> int:
        n = len(grid)
        dp = grid[0][:]
        for i in range(1, n):
            min1, min2, idx1 = float('inf'), float('inf'), -1
            for j in range(n):
                if dp[j] < min1:
                    min2, min1, idx1 = min1, dp[j], j
                elif dp[j] < min2:
                    min2 = dp[j]
            ndp = [0] * n
            for j in range(n):
                ndp[j] = grid[i][j] + (min2 if j == idx1 else min1)
            dp = ndp
        return min(dp)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn min_falling_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut dp = grid[0].clone();
        for i in 1..n {
            let (mut min1, mut min2, mut idx1) = (i32::MAX, i32::MAX, -1);
            for j in 0..n {
                if dp[j] < min1 {
                    min2 = min1; min1 = dp[j]; idx1 = j as i32;
                } else if dp[j] < min2 {
                    min2 = dp[j];
                }
            }
            let mut ndp = vec![0; n];
            for j in 0..n {
                ndp[j] = grid[i][j] + if j as i32 == idx1 { min2 } else { min1 };
            }
            dp = ndp;
        }
        *dp.iter().min().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    minFallingPathSum(grid: number[][]): number {
        const n = grid.length;
        let dp = grid[0].slice();
        for (let i = 1; i < n; ++i) {
            let min1 = Infinity, min2 = Infinity, idx1 = -1;
            for (let j = 0; j < n; ++j) {
                if (dp[j] < min1) {
                    min2 = min1; min1 = dp[j]; idx1 = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j];
                }
            }
            const ndp = Array(n).fill(0);
            for (let j = 0; j < n; ++j) {
                ndp[j] = grid[i][j] + (j === idx1 ? min2 : min1);
            }
            dp = ndp;
        }
        return Math.min(...dp);
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each cell, we scan all columns in each row.
  • 🧺 Space complexity: O(n) — For the DP array.