Minimum Falling Path Sum

Medium
320.

Minimum Falling Path Sum

Minimum Falling Path Sum is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Bloomberg and Dream11 interviews.

Given an n × n array of integers matrix, return the minimum sum of any falling path through it.

A falling path picks one element from each row, and consecutive picks must be in the same column or in a column differing by one.

Example 1

Input
matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output
13
Explanation
One minimum path is 1 → 5 → 7.

Example 2

Input
matrix = [[-19,57],[-40,-5]]
Output
-59

Example 3

Input
matrix = [[7]]
Output
7

Constraints

  • 1 <= matrix.length <= 8
  • matrix[i].length == matrix.length
  • -100 <= matrix[i][j] <= 100
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[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

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

Minimum Falling Path Sum is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Bloomberg and Dream11 interviews.

Problem statement

Given an n × n array of integers matrix, return the minimum sum of any falling path through it.

A falling path picks one element from each row, and consecutive picks must be in the same column or in a column differing by one.

Example 1

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: One minimum path is 1 → 5 → 7.

Example 2

Input: matrix = [[-19,57],[-40,-5]]
Output: -59

Example 3

Input: matrix = [[7]]
Output: 7

Constraints

  • 1 <= matrix.length <= 8
  • matrix[i].length == matrix.length
  • -100 <= matrix[i][j] <= 100

Hints for Minimum Falling Path Sum

  1. Hint 1

    Process the rows top to bottom, keeping the best cost to reach each column of the current row.

  2. Hint 2

    A cell can be reached from directly above or from either diagonal, so take the minimum of those three.

  3. Hint 3

    Only the previous row matters — one array of length n suffices.

How to solve Minimum Falling Path Sum

Process rows top to bottom keeping the cheapest cost to reach each column; each cell takes the min of the three cells above it (up, up-left, up-right).

Approach

  1. Start dp = matrix[0].
  2. For each following row, nxt[c] = matrix[r][c] + min(dp[c-1], dp[c], dp[c+1]) with bounds respected.
  3. Return min(dp).

Why it works

A falling path enters each cell from one of exactly three predecessors, so the best cost decomposes over that choice and only the previous row is needed.

Complexity

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

Pitfalls

  • Take the minimum over the whole last row — the path may end anywhere.

Reference solution

Python

def minFallingPathSum(matrix) -> int:
    n = len(matrix)
    dp = list(matrix[0])
    for r in range(1, n):
        nxt = []
        for c in range(n):
            best = dp[c]
            if c > 0:
                best = min(best, dp[c - 1])
            if c + 1 < n:
                best = min(best, dp[c + 1])
            nxt.append(matrix[r][c] + best)
        dp = nxt
    return min(dp)

Java

public static int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int[] dp = Arrays.copyOf(matrix[0], n);
    for (int r = 1; r < n; r++) {
        int[] next = new int[n];
        for (int c = 0; c < n; c++) {
            int best = dp[c];
            if (c > 0) best = Math.min(best, dp[c - 1]);
            if (c + 1 < n) best = Math.min(best, dp[c + 1]);
            next[c] = matrix[r][c] + best;
        }
        dp = next;
    }
    int answer = dp[0];
    for (int c = 1; c < n; c++) answer = Math.min(answer, dp[c]);
    return answer;
}

C++

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = (int) matrix.size();
    vector<int> dp = matrix[0];
    for (int r = 1; r < n; r++) {
        vector<int> next(n, 0);
        for (int c = 0; c < n; c++) {
            int best = dp[c];
            if (c > 0) best = min(best, dp[c - 1]);
            if (c + 1 < n) best = min(best, dp[c + 1]);
            next[c] = matrix[r][c] + best;
        }
        dp = next;
    }
    return *min_element(dp.begin(), dp.end());
}

JavaScript

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    let dp = matrix[0].slice();
    for (let r = 1; r < n; r++) {
        const next = [];
        for (let c = 0; c < n; c++) {
            let best = dp[c];
            if (c > 0 && dp[c - 1] < best) best = dp[c - 1];
            if (c + 1 < n && dp[c + 1] < best) best = dp[c + 1];
            next.push(matrix[r][c] + best);
        }
        dp = next;
    }
    let answer = dp[0];
    for (let c = 1; c < n; c++) {
        if (dp[c] < answer) answer = dp[c];
    }
    return answer;
};

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