Minimum Falling Path Sum - Solution & Explanation
Problem Statement
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).
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.
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
Approach Overview
Problem Overview: You are given an n x n matrix of integers. A falling path starts at any cell in the first row and moves to the next row either directly below, diagonally left, or diagonally right. The goal is to compute the minimum possible sum of values along any valid falling path from the top row to the bottom row.
Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))
This approach models the problem as recursion over rows. For each cell (r, c), recursively compute the minimum path sum starting from that cell by exploring the three valid next positions: (r+1, c-1), (r+1, c), and (r+1, c+1). Many subproblems repeat, so store results in a memo table to avoid recomputation. Each cell is solved once, which reduces exponential recursion to quadratic time. This method is intuitive if you think in terms of exploring all paths but caching results.
The recursion stops when the last row is reached. Out-of-bound column moves are ignored. Because every matrix cell is computed once and stored, the complexity becomes O(n^2). This pattern is common in dynamic programming problems on grids.
Approach 2: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n^2) or O(1) in-place)
The bottom-up strategy processes the matrix row by row. Starting from the second row, update each cell by adding the minimum of the three reachable cells from the previous row: up-left, up, and up-right. This converts the matrix into a DP table where each entry represents the minimum path sum reaching that cell.
For cell (r, c), compute matrix[r][c] += min(prev[c], prev[c-1], prev[c+1]) while handling boundary columns carefully. After processing all rows, the answer is the minimum value in the last row. This method iterates once over the grid and avoids recursion overhead. Because the DP values can overwrite the original matrix, the extra space can be reduced to O(1).
This technique is typical for problems involving transitions in a matrix or grid where each state depends on nearby cells. Iterating through the array structure row by row keeps the implementation simple and efficient.
Recommended for interviews: Bottom-up dynamic programming is the expected solution. It demonstrates that you can convert recursive state transitions into iterative DP and optimize space if needed. Showing the top-down memoized version first can help explain the recurrence, but the bottom-up implementation signals stronger DP problem-solving skills.
Approach 1: Bottom-Up Dynamic Programming Approach
Using a dynamic programming matrix, you can start from the second-last row of the matrix and calculate the minimum path sum by traversing through possible paths (directly below, diagonally left, and diagonally right). Update the matrix in-place to use constant space.
In the C solution, we iterate from the second-last row to the first row, and for each element, we compute the minimum sum from possible paths below. We update the original matrix with these minimum values and finally compute the minimum value in the first row.
Complexity
Time Complexity: O(n^2) because each element is visited once.
Space Complexity: O(1) since the computations are done in place.
Approach 2: Top-Down Dynamic Programming with Memoization
For this approach, we use recursion with memoization to explore paths starting from the first row to the last row. We store intermediate results to avoid redundant calculations.
In the C solution, a recursive function with memoization is used to compute the minimum falling path sum starting from every element in the first row. The memo table avoids recalculation of already known results.
Complexity
Time Complexity: O(n^2) due to memoization reducing redundant calculations.
Space Complexity: O(n^2) due to the memoization table.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bottom-Up Dynamic Programming Approach | Time Complexity: O(n^2) because each element is visited once. |
| Top-Down Dynamic Programming with Memoization | Time Complexity: O(n^2) due to memoization reducing redundant calculations. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Top-Down DP with Memoization | O(n^2) | O(n^2) | When deriving the recurrence relation or explaining the problem using recursion |
| Bottom-Up Dynamic Programming | O(n^2) | O(n^2) or O(1) in-place | Preferred for production or interviews due to iterative structure and possible space optimization |
Video Solution
Minimum Falling Path Sum | Recursion | Memo | Bottom Up | Leetcode 931 • codestorywithMIK • 18,872 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Falling Path Sum easy or hard?
How to solve Minimum Falling Path Sum in O(n)?
What is the best approach for Minimum Falling Path Sum?
What data structure is used in Minimum Falling Path Sum?
What is the time complexity of Minimum Falling Path Sum?
Minimum Falling Path Sum Python or Java solution approach
Is Minimum Falling Path Sum asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Minimum Falling Path Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor