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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Minimum Falling Path Sum 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 →