Minimum Falling Path Sum

Minimum Falling Path Sum

1. What is this problem about?

The Minimum Falling Path Sum is a classic matrix optimization problem. You are given an $n \times n$ grid of integers. A "falling path" starts at any element in the first row and ends in the last row. From a cell $(row, col)$, you can move to the three cells directly below it: $(row+1, col-1)$, $(row+1, col)$, and $(row+1, col+1)$. The goal is to find the minimum total sum of any such path.

2. Why is this asked in interviews?

This is one of the most frequently asked Dynamic Programming questions at companies like Goldman Sachs and Microsoft. The Minimum Falling Path Sum interview question is a perfect introduction to 2D DP. It tests if you can identify subproblems (the min path sum to a specific cell) and build a solution iteratively. It's a foundational problem for understanding how information flows through a grid in optimization tasks.

3. Algorithmic pattern used

The algorithmic pattern used is Dynamic Programming. Let dp[i][j] be the minimum falling path sum ending at cell (i, j). The value of dp[i][j] is the value of grid[i][j] plus the minimum of the three possible cells from the previous row: dp[i-1][j-1], dp[i-1][j], and dp[i-1][j+1]. By filling this table row by row, the answer will be the minimum value in the last row of the dp table. This "Matrix, Dynamic Programming interview pattern" is robust and efficient.

4. Example explanation

Matrix: [2, 1, 3] [6, 5, 4] [7, 8, 9]

• Row 0 remains: [2, 1, 3]
• Row 1:
  • dp[1][0] = 6 + min(2, 1) = 7
  • dp[1][1] = 5 + min(2, 1, 3) = 6
  • dp[1][2] = 4 + min(1, 3) = 5 Row 1 becomes: [7, 6, 5]
• Row 2:
  • dp[2][0] = 7 + min(7, 6) = 13
  • dp[2][1] = 8 + min(7, 6, 5) = 13
  • dp[2][2] = 9 + min(6, 5) = 14 Min in last row is 13.

5. Common mistakes candidates make

A common mistake in the Minimum Falling Path Sum coding problem is not handling the boundary conditions (the first and last columns) correctly. When you are in the first column, there is no "diagonal left" cell. Another mistake is using extra space $O(N^2)$ when you can solve it in-place or using only $O(N)$ extra space (since you only ever need the previous row). Many candidates also forget to take the minimum of the entire last row as their final answer.

6. Interview preparation tip

Practice "in-place" DP for grid problems to show you care about space optimization. Also, always check if you can reduce a 2D DP to a 1D DP. For grid problems where you only move one row at a time, you usually only need two rows (current and previous) or even just one row if you update carefully. This is a key "Dynamic Programming optimization pattern."