Minimum Falling Path Sum II

Hard
882.

Minimum Falling Path Sum II

Minimum Falling Path Sum II is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minFallingPathSum = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Falling Path Sum II — Solution in Python, Java & C++

Minimum Falling Path Sum II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Falling Path Sum II is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Adobe interviews.

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

Hints for Minimum Falling Path Sum II

  1. Hint 1

    Row by row, only the previous row's best totals matter.

  2. Hint 2

    For a given column you need the best previous total from a different column.

  3. Hint 3

    That is the previous row's minimum, unless the minimum sits in this very column — then it is the second minimum.

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

  1. Start with the first row as the running totals.
  2. For each next row, find the smallest previous total and its column, plus the second smallest.
  3. Each cell adds the smallest — or the second smallest when the smallest came from its own column.
  4. 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)

Java

public static int minFallingPathSum(int[][] grid) {
    int n = grid.length;
    int[] prev = grid[0].clone();
    for (int i = 1; i < n; i++) {
        int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE, i1 = -1;
        for (int k = 0; k < n; k++) {
            if (prev[k] < m1) {
                m2 = m1;
                m1 = prev[k];
                i1 = k;
            } else if (prev[k] < m2) {
                m2 = prev[k];
            }
        }
        int[] cur = new int[n];
        for (int j = 0; j < n; j++) cur[j] = grid[i][j] + (j == i1 ? m2 : m1);
        prev = cur;
    }
    int best = prev[0];
    for (int k = 1; k < n; k++) best = Math.min(best, prev[k]);
    return best;
}

C++

int minFallingPathSum(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    vector<int> prev = grid[0];
    for (int i = 1; i < n; i++) {
        int m1 = INT_MAX, m2 = INT_MAX, i1 = -1;
        for (int k = 0; k < n; k++) {
            if (prev[k] < m1) {
                m2 = m1;
                m1 = prev[k];
                i1 = k;
            } else if (prev[k] < m2) {
                m2 = prev[k];
            }
        }
        vector<int> cur(n);
        for (int j = 0; j < n; j++) cur[j] = grid[i][j] + (j == i1 ? m2 : m1);
        prev = cur;
    }
    return *min_element(prev.begin(), prev.end());
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming