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).
Here’s the [Problem Link] to begin with.
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
Solution 1: Brute Force (Recursion)
Intuition
At cell (i, j), you have three choices moving up the rows:
- Move from top-left
(i-1, j-1) - Move from top
(i-1, j) - Move from top-right
(i-1, j+1)
Try all possible paths recursively for every starting position in the last row, and take the minimum.
Approach
- Base case: If you’ve moved out of bounds (j < 0 or j ≥ columns), return infinity. If you’re at the top row, return the matrix value.
- Recursive case: From each cell, calculate sum using left, up, and right moves; add current cell’s value and propagate min sum upward.
Code
class Solution:
def solve(self, i, j, matrix):
# Out of bounds, set as infinite to avoid considering
if j < 0 or j >= len(matrix[0]):
return float("inf")
# Top row: path sum is just the value itself
if i == 0:
return matrix[0][j]
# Take min of possible paths to (i, j)
left = self.solve(i - 1, j - 1, matrix)
up = self.solve(i - 1, j, matrix)
right = self.solve(i - 1, j + 1, matrix)
# Return cell value plus min path sum from above
return matrix[i][j] + min(left, up, right)
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
rows = len(matrix)
cols = len(matrix[0])
mini = float("inf")
# Try each position in the last row as an end point
for j in range(cols):
mini = min(mini, self.solve(rows - 1, j, matrix))
return miniCode Explanation
- From every possible last cell in the bottom row, recursively compute all valid upward falling paths.
- Every call checks three possible “moves”: from diagonal left, above, or diagonal right.
- The recursion explores every path, returning the minimum overall.
Time and Space Complexity
- Time: O(3^rows) (because each step recursively branches into up to three calls)
- Space: O(rows) (stack recursion depth)
Simplified
A pure, all-paths brute force. Simple for small matrices, but very inefficient for larger ones.
Solution 2: Memoization (Top-Down DP)
Intuition
Many subproblems (“min path sum from position (i, j)”) repeat, so use a DP table dp[i][j] to store computed answers. Always check if a sub-result was computed before recursing!
Approach
- Create a DP grid, initialized to
None. - Before each recursion, see if result for that position exists. If so, just return it!
- Save and reuse results to avoid redundant computation.
Code
class Solution:
def solve(self, i, j, matrix, dp):
# Out of bounds in column
if j < 0 or j >= len(matrix[0]):
return float("inf")
# Top row
if i == 0:
return matrix[0][j]
# If already computed, use memoized result
if dp[i][j] is not None:
return dp[i][j]
# Compute possible paths
left = matrix[i][j] + self.solve(i - 1, j - 1, matrix, dp)
up = matrix[i][j] + self.solve(i - 1, j, matrix, dp)
right = matrix[i][j] + self.solve(i - 1, j + 1, matrix, dp)
dp[i][j] = min(left, up, right)
return dp[i][j]
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
rows = len(matrix)
cols = len(matrix[0])
dp = [[None for _ in range(cols)] for _ in range(cols)]
mini = float("inf")
for j in range(cols):
mini = min(mini, self.solve(rows - 1, j, matrix, dp))
return miniCode Explanation
- For every bottom cell, recursively finds min falling path sum but now with memorization.
- Memoization grid
dp[i][j]means every cell is solved once and then reused. - Significantly speeds up brute force, ideal for larger matrices.
Time and Space Complexity
- Time: O(rows × cols)
- Space: O(rows × cols) for dp + O(rows) stack
Simplified
No recalculation, no waste. Typical recursive DP, great for clarity and speed!
Solution 3: Tabulation (Bottom-Up DP)
Intuition
Work from top row downward, filling a DP table:
At every cell in row i, col j: take the cell value plus the minimal path from top, top-left, and top-right of the previous row.
Approach
- DP grid
dp[i][j]: min path sum to (i, j) from row 0. - Set dp[j] = matrix[j] for all columns (base case).
- For all rows:
- For leftmost column, top-left is infinity.
- For rightmost column, top-right is infinity.
- Each cell: add cell value + min(left, up, right).
Code
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
rows = len(matrix)
cols = len(matrix[0])
dp = [[None for _ in range(cols)] for _ in range(rows)]
# Base case: top row same as matrix
for j in range(cols):
dp[0][j] = matrix[0][j]
# Fill for each row below
for i in range(1, rows):
for j in range(0, cols):
# For leftmost, top-left is invalid
if j == 0:
left = float("inf")
else:
left = matrix[i][j] + dp[i - 1][j - 1]
# Always valid: up
up = matrix[i][j] + dp[i - 1][j]
# For rightmost, top-right is invalid
if j == cols - 1:
right = float("inf")
else:
right = matrix[i][j] + dp[i - 1][j + 1]
# Store minimum path sum for cell
dp[i][j] = min(left, up, right)
# Minimum in the last row is the answer
mini = float("inf")
for j in range(cols):
mini = min(mini, dp[rows - 1][j])
return miniCode Explanation
- Start with the first row’s values (base).
- For each cell, consider three reachable cells from the previous row.
- Fill the DP table row by row; last row contains the min answers.
Time and Space Complexity
- Time: O(rows × cols)
- Space: O(rows × cols)
Simplified
Classic bottom-up DP; reliable, easy to debug, and clear state transitions.
Solution 4: Tabulation (Space Optimization)
Intuition
You only need the previous row to compute the current row. Use two 1D arrays (prev and curr), rolling through the matrix row by row.
Approach
prev[j]contains DP values for previous row.- For each row, fill out a new current array, then assign curr to prev for the next row.
- Final row only in
prev.
Code
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
rows = len(matrix)
cols = len(matrix[0])
prev = [None for _ in range(cols)]
# Initialize with the first row
for j in range(cols):
prev[j] = matrix[0][j]
# For each row below, use rolling arrays
for i in range(1, rows):
curr = [None] * cols
for j in range(0, cols):
# For leftmost, top-left is invalid
if j == 0:
left = float("inf")
else:
left = matrix[i][j] + prev[j - 1]
# Always valid: up
up = matrix[i][j] + prev[j]
# For rightmost, top-right is invalid
if j == cols - 1:
right = float("inf")
else:
right = matrix[i][j] + prev[j + 1]
# Set the min sum for this cell
curr[j] = min(left, up, right)
prev = curr
# Minimum in last row
mini = float("inf")
for j in range(cols):
mini = min(mini, prev[j])
return miniCode Explanation
- Saves on space by needing only one prior row’s DP state.
- Efficient and optimal for coding interviews with size constraints.
Time and Space Complexity
- Time: O(rows × cols)
- Space: O(cols) (just two arrays per step)
Simplified
Ultra-useful rolling array DP pattern, especially for large matrices!
Summary Table
| Approach | Time | Space | Best For |
|---|---|---|---|
| Recursion (Brute Force) | O(3^rows) | O(rows) | Learning, small size |
| Memoization (Top-Down DP) | O(rows·cols) | O(rows·cols) | Efficient, readable |
| Tabulation (Bottom-Up DP) | O(rows·cols) | O(rows·cols) | Systematic DP |
| Space-Optimized Tabulation | O(rows·cols) | O(cols) | Large limits, coding |
Conclusion
Minimum Falling Path Sum is an excellent test of dynamic programming mastery. Start with recursion, then build up to memoization and tabulation, and always end with the most space-optimal version for real interview success. Practice with more DP problems and always look for ways to reduce space without sacrificing clarity!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
