Skip to main content

1289. Minimum Falling Path Sum II

hard

Minimum sum of a falling path through an n x n grid where consecutive picks must come from different columns. Naive DP is O(n^3); the speedup keeps the two smallest values from the previous row and answers each cell in O(1).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts. A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

Constraints

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

Examples

Example 1

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

Explanation: The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9]. The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2

Input
grid = [[7]]
Output
7

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive dp[i][j] = grid[i][j] + min over k != j of dp[i-1][k] is O(n^3). For each row, that inner min over k != j is the bottleneck.

Hint 2

Per row, the min over k != j only differs for the column that holds the minimum value. So precompute, for the previous row, the smallest and second-smallest values along with the column of the smallest.

Hint 3

If j == minColumn, use second smallest; otherwise use the smallest. That makes each cell O(1).

Hint 4

Only the previous row's two scalars are needed — O(1) extra space if you don't store the full grid.

Solution approach

Reveal approach

Bottom-up DP with row compression. For row i, compute the smallest value firstMin, its column firstIdx, and the second smallest value secondMin from the previous row. For each column j of the current row, dp[i][j] = grid[i][j] + (j == firstIdx ? secondMin : firstMin). After filling row i, recompute (firstMin, firstIdx, secondMin) over row i's dp values for use by row i+1. The first row is just grid[0]. The answer is the smallest value in the last row. Storing only the rolling triplet gives O(1) auxiliary space beyond the input.

Complexity

Time
O(n^2)
Space
O(n)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Minimum Falling Path Sum II and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →