Problem Description

You are given an n x n matrix of integers. Your task is to find the minimum sum of any falling path through the matrix.

A falling path is defined as follows:

• Start at any element in the first row
• From each position (row, col), you can move to the next row by choosing one of three positions:
  • (row + 1, col - 1) - diagonally left
  • (row + 1, col) - directly below
  • (row + 1, col + 1) - diagonally right
• Continue this process until you reach the last row
• The path must stay within the matrix boundaries

The sum of a falling path is the total of all elements visited along the path. You need to find the path that gives the smallest possible sum.

For example, if you have a 3x3 matrix, you could start at any element in row 0, then move to one of the three allowed positions in row 1, and finally to one of the three allowed positions in row 2. The goal is to find which combination of moves produces the minimum sum.

The solution uses dynamic programming where f[j] represents the minimum sum to reach position j in the current row. For each new row, it calculates the minimum sum to reach each position by considering all valid previous positions (up to 3 positions from the previous row) and adding the current element's value. The final answer is the minimum value in the last row's results.

Intuition

The key insight is that we need to find the optimal path from top to bottom, and at each step, we have limited choices. This naturally suggests a dynamic programming approach.

Think about it this way: if we're standing at any position in a row, the minimum sum to reach that position depends on which position we came from in the previous row. Since we can only arrive from three possible positions (directly above, diagonally left-above, or diagonally right-above), we just need to pick the one that gives us the smallest cumulative sum.

Instead of trying all possible paths from the top (which would be exponential in complexity), we can build up the solution row by row. For each position in the current row, we ask: "What's the minimum sum needed to reach this position?" The answer is the minimum sum to reach any of the valid previous positions, plus the current cell's value.

The beauty of this approach is that we don't need to keep track of the entire path - we only need to know the minimum sums to reach each position in the previous row. This is why the solution uses two arrays: f stores the minimum sums for the previous row, and g calculates the minimum sums for the current row.

The expression min(f[l:r]) + x captures this perfectly: it finds the minimum among the valid previous positions (considering boundary constraints with max(0, j-1) and min(n, j+2)) and adds the current element's value. By processing each row sequentially, we guarantee that when we reach the last row, we have the minimum sum to reach each position in that row. The final answer is simply the minimum among all positions in the last row.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a space-optimized dynamic programming approach using a row-by-row processing strategy.

Data Structure:

• We use a 1D array f of size n to store the minimum path sums for the previous row
• A temporary array g of the same size to compute the minimum path sums for the current row

Algorithm Steps:

1. Initialize: Start with f = [0] * n, representing that we haven't processed any rows yet (the cost to reach the "row before" the first row is 0).

2. Process each row: For each row in the matrix:

   • Create a new array g to store the minimum sums for the current row
   • For each position j with value x in the current row:
     • Calculate the valid range of previous positions:
       • l = max(0, j - 1) ensures we don't go below index 0
       • r = min(n, j + 2) ensures we don't exceed the array bounds (note: j + 2 because Python slicing is exclusive of the end)
     • Compute g[j] = min(f[l:r]) + x
       • f[l:r] gives us the slice of valid previous positions (could be 1, 2, or 3 positions depending on boundaries)
       • min(f[l:r]) finds the minimum sum among those valid positions
       • Adding x gives us the minimum sum to reach position j in the current row
   • After processing all positions in the current row, update f = g to prepare for the next row

3. Return the result: After processing all rows, f contains the minimum sums to reach each position in the last row. Return min(f) to get the overall minimum falling path sum.

Time Complexity: O(n²) where n is the dimension of the matrix. We process each of the n² elements once, and for each element, we perform a constant-time operation (finding minimum among at most 3 values).

Space Complexity: O(n) as we only maintain two arrays of size n at any time, rather than storing the entire DP table of size n².

The elegance of this solution lies in its space optimization - instead of maintaining a 2D DP table, we only keep track of the previous row's results, which is sufficient for computing the current row's minimum sums.

Example Walkthrough

Let's walk through a small example with this 3×3 matrix:

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

Goal: Find the minimum sum falling path from top to bottom.

Step 1: Initialize

• f = [0, 0, 0] (no cost to reach positions before the first row)

Step 2: Process Row 0 [2, 1, 3]

• Create g = [0, 0, 0] for storing new values
• For position 0 (value=2):
  • Valid previous positions: l=max(0,0-1)=0, r=min(3,0+2)=2
  • f[0:2] = [0, 0], minimum is 0
  • g[0] = 0 + 2 = 2
• For position 1 (value=1):
  • Valid previous positions: l=max(0,1-1)=0, r=min(3,1+2)=3
  • f[0:3] = [0, 0, 0], minimum is 0
  • g[1] = 0 + 1 = 1
• For position 2 (value=3):
  • Valid previous positions: l=max(0,2-1)=1, r=min(3,2+2)=3
  • f[1:3] = [0, 0], minimum is 0
  • g[2] = 0 + 3 = 3
• Update: f = [2, 1, 3]

Step 3: Process Row 1 [6, 5, 4]

• Create g = [0, 0, 0]
• For position 0 (value=6):
  • Can come from positions 0 or 1 in previous row
  • f[0:2] = [2, 1], minimum is 1
  • g[0] = 1 + 6 = 7
• For position 1 (value=5):
  • Can come from positions 0, 1, or 2 in previous row
  • f[0:3] = [2, 1, 3], minimum is 1
  • g[1] = 1 + 5 = 6
• For position 2 (value=4):
  • Can come from positions 1 or 2 in previous row
  • f[1:3] = [1, 3], minimum is 1
  • g[2] = 1 + 4 = 5
• Update: f = [7, 6, 5]

Step 4: Process Row 2 [7, 8, 9]

• Create g = [0, 0, 0]
• For position 0 (value=7):
  • Can come from positions 0 or 1 in previous row
  • f[0:2] = [7, 6], minimum is 6
  • g[0] = 6 + 7 = 13
• For position 1 (value=8):
  • Can come from positions 0, 1, or 2 in previous row
  • f[0:3] = [7, 6, 5], minimum is 5
  • g[1] = 5 + 8 = 13
• For position 2 (value=9):
  • Can come from positions 1 or 2 in previous row
  • f[1:3] = [6, 5], minimum is 5
  • g[2] = 5 + 9 = 14
• Update: f = [13, 13, 14]

Step 5: Return Result

• min(f) = min([13, 13, 14]) = 13

The minimum falling path sum is 13, which corresponds to the path: 1 → 5 → 7 (or alternatively 1 → 4 → 8).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm iterates through each row of the n×n matrix (outer loop runs n times). For each row, it iterates through each element (inner loop runs n times). Within the inner loop, the slicing operation f[l:r] and min() function take at most O(3) time since we're only considering at most 3 adjacent elements from the previous row. Therefore, the overall time complexity is O(n) × O(n) × O(1) = O(n²).

Space Complexity: O(n)

The algorithm uses two arrays f and g, each of size n, to store the minimum falling path sums. Instead of maintaining the entire DP table of size n×n, it optimizes space by only keeping track of the previous row's results in f and computing the current row's results in g. The space used is O(n) + O(n) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Handling in Column Range Calculation

One of the most common mistakes is incorrectly calculating the valid column range from the previous row, especially with the slicing bounds.

Pitfall Example:

# INCORRECT: Using wrong bounds
left_bound = j - 1  # Can be negative!
right_bound = j + 1  # Misses the rightmost valid column

# This would cause:
# - IndexError when j = 0 (left_bound = -1)
# - Missing valid transitions when using previous_row_dp[left_bound:right_bound]

Correct Solution:

# CORRECT: Properly handle boundaries
left_bound = max(0, j - 1)        # Ensures non-negative index
right_bound = min(n, j + 2)       # j+2 because slicing is exclusive of end

# This ensures:
# - When j = 0: can come from columns [0, 1]
# - When j = n-1: can come from columns [n-2, n-1]
# - When 0 < j < n-1: can come from columns [j-1, j, j+1]

2. Initializing the DP Array with Wrong Values

Another pitfall is initializing the first row's DP values incorrectly.

Pitfall Example:

# INCORRECT: Initializing with the first row values
previous_row_dp = matrix[0]  # Creates a reference, not a copy!
# Or
previous_row_dp = [float('inf')] * n  # Wrong initial values

# This causes incorrect calculations for the second row

Correct Solution:

# CORRECT: Initialize with zeros
previous_row_dp = [0] * n

# The first iteration will correctly compute:
# current_row_dp[j] = min([0, 0, ...]) + matrix[0][j] = matrix[0][j]
# This properly sets up the base case

3. Modifying Arrays In-Place Without Proper Copying

A subtle but critical error occurs when trying to optimize space by reusing arrays incorrectly.

Pitfall Example:

# INCORRECT: Modifying the same array in place
dp = [0] * n
for row in matrix:
    for j, x in enumerate(row):
        # Modifying dp while still reading from it!
        dp[j] = min(dp[max(0, j-1):min(n, j+2)]) + x
        # This corrupts the values needed for subsequent columns

Correct Solution:

# CORRECT: Use two separate arrays
previous_row_dp = [0] * n
for row in matrix:
    current_row_dp = [0] * n  # Fresh array for current row
    for j, x in enumerate(row):
        current_row_dp[j] = min(previous_row_dp[max(0, j-1):min(n, j+2)]) + x
    previous_row_dp = current_row_dp  # Safe to reassign after processing entire row

4. Edge Case: Single Element Matrix

While the provided solution handles this correctly, it's worth noting that some implementations might fail on a 1x1 matrix.

Pitfall Example:

# INCORRECT: Assuming matrix has at least 2 rows
def minFallingPathSum(self, matrix):
    n = len(matrix)
    dp = matrix[0][:]  # Copy first row
    for i in range(1, n):  # Skips if n = 1!
        # ... process rows
    return min(dp)

Correct Solution: The provided solution naturally handles this case because:

• With n=1, there's only one iteration
• min([0]) + matrix[0][0] correctly returns the single element
• No special case handling needed