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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →