Domain 2MediumMEDIUM

Minimum Falling Path Sum

Find the minimum sum of a falling path through an n x n matrix using dynamic programming with O(N) auxiliary space.

Domain: medium•Updated: 2026-09-04
#dynamic programming#matrix#O(N^2)#O(N) space

Problem Breakdown

We are given an n x n integer matrix and asked to find the minimum sum of a “falling path” from any element in the first row down to the last row. A falling path moves one step at a time, always increasing the row index by 1 (row + 1). From position (r, c), we can move to (r+1, c-1) (diagonal left), (r+1, c) (directly below), or (r+1, c+1) (diagonal right).

Inputs: An n x n matrix of integers. Outputs: A single integer representing the minimum path sum. Constraints & Edge Cases:

  • Size: NN is between 1 and 100. This allows for an O(N2)O(N^2) solution comfortably within time limits (approx. 10,000 operations).
  • Values: Integers can be negative (-100 to 100), so the minimum sum could be negative. We must initialize our DP state carefully if using a min-accumulation approach, though standard addition works fine here since we are minimizing sums of actual values (not absolute differences).
  • Boundaries: When at column 0 or n-1, diagonal moves to -1 or +1 indices do not exist. We must handle these boundary checks explicitly in the logic.

Intuition

A naive brute-force approach would try every possible path from top-left (or any start) to bottom-right. Since we have 3 choices at each step, there are roughly 3N−13^{N-1} paths per starting cell. With multiple starting cells and a matrix size of up to 100, this exponential complexity (O(3N)O(3^N)) is infeasible.

However, notice that the optimal path ending at any specific cell (i, j) depends only on the minimum cost to reach its valid neighbors in row i-1. This exhibits optimal substructure and overlapping subproblems, which are hallmarks of Dynamic Programming (DP). We can compute the minimum falling path sum for each cell based on values from the previous row, building up our solution bottom-up.

Approach

We will use a space-optimized DP approach where we only need to store the results of the current and previous rows.

  1. Initialize a dp array with the first row’s values (representing min path sums ending at each column in row 0).
  2. Iterate through subsequent rows from index 1 to n−1n-1.
  3. For each cell (i, j), calculate its minimum falling path sum by adding matrix[i][j] to the minimum of valid neighbors in the previous row (dp[j-1], dp[j], dp[j+1]). Handle boundary checks for columns 0 and n−1n-1.
  4. Update our DP state with these new values (effectively moving from “previous row” to “current row”).
  5. After processing the last row, return the minimum value in that final DP array.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We visit every cell in the matrix exactly once (N×NN \times N), performing constant-time operations (min of 3 values). Given N=100N=100, this is roughly 10,000 operations.
  • Space Complexity: O(N)O(N) auxiliary space for our DP array storing one row’s results at a time. If we were allowed to modify the input matrix in-place, it could be reduced to O(1)O(1) extra space (excluding input storage).

Solution

from typing import List

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        
        # Initialize dp array with the first row values. 
        # This represents the minimum path sum ending at each column of the previous processed row.
        prev_row = matrix[0][:] 
        
        for r in range(1, n):
            curr_row = [float('inf')] * n
            for c in range(n):
                # Determine valid neighbors from the previous row (r-1)
                left_val = prev_row[c - 1] if c > 0 else float('inf')
                mid_val = prev_row[c]
                right_val = prev_row[c + 1] if c < n - 1 else float('inf')
                
                # Calculate min path sum for current cell (r, c)
                curr_row[c] = matrix[r][c] + min(left_val, mid_val, right_val)
            
            # Move to next row: update prev_row reference
            prev_row = curr_row
            
        return min(prev_row)

Edge Cases Handled

  • Single Element Matrix (N=1N=1): The loop range(1, n) will not execute. We initialize with the single element and immediately return it via min(), which is correct behavior for Example 3.
  • Boundary Columns: Logic checks c > 0 and c < n - 1. If a column has no left or right neighbor in the previous row, we treat that direction as infinity (float('inf')) so it won’t be selected by min(), effectively ignoring invalid moves.
  • Negative Values: Since we are summing values (not taking absolute differences), negative numbers naturally reduce the total path sum. The logic holds without modification because standard addition works correctly with negatives in this minimization context.