Minimum Falling Path Sum II — Hard Problem & Solution

A falling path with non-zero shifts picks exactly one element from each row of the n × n grid, with no two picks from adjacent rows in the same column.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A falling path with non-zero shifts picks exactly one element from each row of the n × n grid, with no two picks from adjacent rows in the same column.

Return the minimum sum of such a path.

Example 1

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 1 → 5 → 7.

Example 2

Input: grid = [[7]]
Output: 7
Explanation: A single row has nothing to avoid.

Example 3

Input: grid = [[-73,61,43,-48,-36],[3,30,27,57,10],[96,-76,84,59,-15],[5,-49,76,31,-7],[97,91,61,-46,67]]
Output: -192

Constraints

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

How to solve Minimum Falling Path Sum II

The naive transition scans all n previous columns per cell, which is O(n³). But the only value that can be blocked is the single best one, so tracking the best and second-best of each row makes each transition O(1).

Approach

Start with the first row as the running totals.
For each next row, find the smallest previous total and its column, plus the second smallest.
Each cell adds the smallest — or the second smallest when the smallest came from its own column.
The answer is the minimum of the final row.

Why it works

Only one previous column is forbidden, so at most one candidate is removed from consideration; the second-best is therefore always available and is the best legal alternative. That makes the two values sufficient to answer every cell in the row.

Complexity

Time — O(n²)
Space — O(n)

Pitfalls

Only the column holding the minimum falls back to the second-best; every other column uses the minimum.
Ties matter: if two columns share the minimum value, the second-best equals it, so no column is penalised — tracking one index handles this correctly.
n = 1 has no constraint to violate and the answer is the single element.

Reference solution

Python

from typing import List

def minFallingPathSum(grid: List[List[int]]) -> int:
    n = len(grid)
    prev = list(grid[0])
    for i in range(1, n):
        m1 = m2 = float("inf")
        i1 = -1
        for k in range(n):
            if prev[k] < m1:
                m2 = m1
                m1 = prev[k]
                i1 = k
            elif prev[k] < m2:
                m2 = prev[k]
        prev = [grid[i][j] + (m2 if j == i1 else m1) for j in range(n)]
    return min(prev)

JavaScript

var minFallingPathSum = function(grid) {
    var n = grid.length;
    var prev = grid[0].slice();
    for (var i = 1; i < n; i++) {
        var m1 = Infinity, i1 = -1, m2 = Infinity, k;
        for (k = 0; k < n; k++) {
            if (prev[k] < m1) { m2 = m1; m1 = prev[k]; i1 = k; }
            else if (prev[k] < m2) m2 = prev[k];
        }
        var cur = [];
        for (var j = 0; j < n; j++) cur.push(grid[i][j] + (j === i1 ? m2 : m1));
        prev = cur;
    }
    var best = prev[0];
    for (k = 1; k < n; k++) if (prev[k] < best) best = prev[k];
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue