Skip to main content

931. Minimum Falling Path Sum

medium

Find the minimum sum of a falling path through an n x n matrix, where each step drops one row and shifts column by at most one. Linear-recurrence DP — the only twist over a top-to-bottom walk is choosing among three parents.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Constraints

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

Examples

Example 1

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

Explanation: There are two falling paths with a minimum sum as shown.

Example 2

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

Explanation: The falling path with a minimum sum is shown.

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

dp[i][j] = minimum sum of a falling path that ends at (i, j).

Hint 2

dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]), treating out-of-bounds parents as +infinity.

Hint 3

Answer is min over the last row. Only the previous row is needed — O(n) extra space.

Solution approach

Reveal approach

Bottom-up DP. dp[i][j] is the minimum falling-path sum ending at cell (i, j). Initialize dp[0][j] = matrix[0][j]. For each row i from 1 to n-1 and each column j, dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) where out-of-bounds parents (j-1 < 0 or j+1 >= n) contribute +infinity. Return the minimum of dp[n-1][*]. Space optimization: keep only the previous row in a 1D array of length n — replace it in place once per row using a temporary for the column to the left so you don't clobber dp[j-1] before reading it. Top-down memoized recursion is equally clean.

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).

  • Amazon
  • Goldman Sachs

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →