Minimum Falling Path Sum II: Multi-Column DP

LeetCode Minimum Falling Path Sum II (problem 1289) asks you to find the minimum sum of a falling path with non-zero shifts. You are given an n x n integer grid. A falling path starts at any element in the first row and chooses one element from each subsequent row. The catch: the element chosen from row i must be in a different column than the element chosen from row i - 1. Return the minimum possible sum.

This is the harder sibling of LeetCode 931. In the original problem, you can only move to adjacent columns (directly below, below-left, or below-right). Here, you can jump to any column, as long as it is not the same one.

Why this problem matters

This problem teaches you an important optimization trick that shows up often in DP problems: instead of scanning all candidates to find the best option for each cell, you can precompute the top candidates and reuse them. The "track two minimums" technique applies to paint house problems, scheduling problems, and any DP where you need the minimum over all elements except one.

The brute force approach

The naive DP approach processes the grid row by row. For each cell in row i, you look at every cell in row i - 1 that is in a different column, and take the minimum.

def min_falling_path_sum(grid):
    n = len(grid)
    for i in range(1, n):
        for j in range(n):
            best = float('inf')
            for k in range(n):
                if k != j:
                    best = min(best, grid[i - 1][k])
            grid[i][j] += best
    return min(grid[-1])

This works, but the three nested loops give it O(n^3) time. For each of the n^2 cells, you scan n columns in the previous row. When n is large (up to 200), that is 8 million operations, which is fine but wasteful. More importantly, the brute force hides the real insight.

The key insight

When you compute the minimum over all columns in row i - 1 except column j, there are really only two cases:

1. If j is not the column where the global minimum lives, you just use the global minimum.
2. If j is the column where the global minimum lives, you use the second-smallest value instead.

That means you only need three pieces of information from the previous row: the smallest value, the second-smallest value, and which column holds the smallest value. With those three numbers, you can fill in every cell of the current row in O(1) time each.

Walking through it step by step

The optimized solution

def min_falling_path_sum(grid: list[list[int]]) -> int:
    n = len(grid)

    for i in range(1, n):
        min1 = min2 = float('inf')
        min1_col = -1
        for j in range(n):
            if grid[i - 1][j] < min1:
                min2 = min1
                min1 = grid[i - 1][j]
                min1_col = j
            elif grid[i - 1][j] < min2:
                min2 = grid[i - 1][j]
        for j in range(n):
            if j == min1_col:
                grid[i][j] += min2
            else:
                grid[i][j] += min1

    return min(grid[-1])

Here is how it works:

1. Start from row 1. Row 0 is the base case and needs no updates.
2. For each row i, scan row i - 1 to find min1 (the smallest value), min1_col (which column it sits in), and min2 (the second-smallest value).
3. For each cell (i, j): if j equals min1_col, add min2 to grid[i][j]. Otherwise, add min1.
4. After processing all rows, the answer is the minimum value in the last row.

The algorithm modifies the grid in place, so no extra space is needed beyond a few variables.

Complexity analysis

Each row requires two linear passes: one to find the two minimums, and one to update the current row. That is 2n work per row across n rows, giving O(n^2) total. The in-place modification means you only need a constant number of extra variables.

Building blocks

1. Tracking the two smallest values

The core trick is maintaining both the smallest and second-smallest values from a collection. This pattern shows up whenever you need "the minimum excluding one element":

min1 = min2 = float('inf')
min1_idx = -1
for idx, val in enumerate(values):
    if val < min1:
        min2 = min1
        min1 = val
        min1_idx = idx
    elif val < min2:
        min2 = val

When you need the minimum excluding index i, check: if i == min1_idx, use min2. Otherwise, use min1. This avoids rescanning the array each time.

2. Row-by-row DP on a matrix

The structure of processing a grid one row at a time, where each cell depends only on values from the previous row, is the same backbone used in many matrix DP problems:

for i in range(1, n):
    precompute_info_from_row(i - 1)
    for j in range(n):
        grid[i][j] += best_from_previous(i, j)

The "precompute" step varies by problem. Here you precompute two minimums. In the original falling path problem, there is nothing to precompute because each cell only looks at three neighbors. The key is recognizing when precomputation can save you a factor of n.

Edge cases

• 1x1 grid: The answer is the single element. No path computation needed.
• 2x2 grid: Each row must pick a different column from the previous row, so there are exactly two paths. The algorithm handles this naturally.
• All values identical: Every valid path has the same sum (n * value). The two minimums are equal, and the algorithm works correctly.
• Negative values: The algorithm handles negatives without any changes, since it always adds the minimum (most negative) value from the previous row.
• Large n (up to 200): The O(n^2) solution handles n = 200 easily with 40,000 operations, compared to 8 million for the brute force.

From understanding to recall

The two-minimum optimization is one of those tricks that feels obvious once you see it, but is surprisingly easy to forget under pressure. During an interview, you might start with the O(n^3) brute force and then struggle to remember how to shave off that inner loop. The key insight to internalize is: "I only need the best and second-best from the previous row, plus which column the best came from."

Spaced repetition locks this pattern into long-term memory. When you revisit this problem after a few days, you will not need to re-derive the optimization. You will immediately see "different column constraint means track two minimums" and write the solution in minutes.

The more DP optimization problems you practice (paint house, scheduling with exclusions, matrix path problems), the more natural this "precompute the top-k candidates" technique becomes. Each variant reinforces the shared structure and sharpens your ability to spot the opportunity.

Related posts

• Minimum Falling Path Sum - The original version with adjacent-column movement
• Dungeon Game - Grid DP with a different optimization challenge
• Triangle - Similar falling path concept on a triangular grid

If you want to move from "I can solve this with hints" to "I can solve this cold in an interview," structured repetition is the fastest path. CodeBricks schedules review sessions that target exactly the problems you are about to forget, keeping your pattern recognition sharp without wasting time on problems you already own.