Minimum Falling Path Sum

Medium15–20 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonBloomberg

Given a square grid, find the minimum possible sum of any "falling path" from the top row to the bottom row — a path that starts at any cell in the top row and, at every later row, moves either straight down or diagonally into the column immediately to its left or right. Every cell's cheapest finish depends only on the (up to three) cells directly above it that could have fallen into it, so working row by row from the top down — where the top row's cheapest finish is simply its own value — lets each row be resolved using results already computed for the row before it. Once every row has been swept through, the smallest value on the last row is the answer, since the path is free to land in whichever column ends up cheapest.

Test Case 1:

Input:matrix = [[3,4,1],[8,2,6],[5,9,3]]

Output:6

Explanation:The path 1→2→3 (top-right, straight down, diagonal-left) totals 6, the smallest of any top-to-bottom falling path.

Test Case 2:

Input:matrix = [[2,5],[4,1]]

Output:3

Explanation:The path 2→1 (top-left, diagonal-right) totals 3, beating 5→1 which totals 6.

Test Case 3:

Input:matrix = [[7]]

Output:7

Explanation:A single-cell grid has only one possible path: the cell itself.

Constraints

◆1 ≤ matrix.length ≤ 20 (a square n×n grid)
◆-100 ≤ matrix[i][j] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

A falling path may start at any cell in the top row, then at every later row it must move to the row directly below — either straight down, or diagonally into the adjacent column on either side. From any cell, the cheapest way to finish is that cell's own value plus whichever of those (up to three) next cells offers the cheapest finish, and stepping off either side edge of the grid simply isn't a valid move. A cell on the very last row has nowhere left to fall, so its cheapest finish is just its own value. Trying every starting column across the top row and recursing downward from each one finds the overall minimum, though the same lower cell ends up recomputed whenever different upper paths funnel into it.

TimeO(3^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[][] matrix;
    private int n;

    public int minFallingPathSum(int[][] matrix) {
        this.matrix = matrix;
        this.n = matrix.length;
        int best = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            best = Math.min(best, solve(0, j));
        }
        return best;
    }

    private int solve(int i, int j) {
        if (j < 0 || j >= n) return Integer.MAX_VALUE;
        if (i == n - 1) return matrix[i][j];
        int best = solve(i + 1, j);
        best = Math.min(best, solve(i + 1, j - 1));
        best = Math.min(best, solve(i + 1, j + 1));
        return matrix[i][j] + best;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for the row currently being processed, the cheapest cost to reach the bottom from each of its cells. Start with the top row's own values, since a path can start anywhere along it. For every row after that, each cell's new cost is its own value plus the cheapest of the up-to-three cells above it that could have fallen into it — straight above, or diagonally in from either side, whichever of those actually exist within the grid. Once every row has been swept through this way, the smallest value remaining is the minimum falling path sum, since the path could have ended at any column on the last row.

TimeO(n²)