LeetCode 931 - Minimum Falling Path Sum

The problem asks for the minimum sum of any falling path through an n x n integer matrix. A falling path is defined as a sequence of elements starting from any element in the first row and moving row by row to the last row.

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 931

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem asks for the minimum sum of any falling path through an n x n integer matrix. A falling path is defined as a sequence of elements starting from any element in the first row and moving row by row to the last row. At each step, the path may move straight down, diagonally left, or diagonally right. The input is a square matrix, so the number of rows equals the number of columns, and each element may be positive, negative, or zero. The output is a single integer representing the minimum sum achievable by any valid falling path.

Constraints indicate the matrix can be up to 100 x 100 in size, and element values range from -100 to 100. This implies brute-force enumeration of all falling paths would be computationally infeasible because there could be up to 3^(n-1) paths, which grows exponentially.

Important edge cases include matrices of size 1 x 1, matrices with all negative numbers, and matrices where the minimum path hugs the edges, testing diagonal movement.

Approaches

The brute-force approach would recursively explore every falling path starting from each element in the first row. For each position (row, col), the algorithm would recursively compute the minimum path sum for positions (row+1, col-1), (row+1, col), and (row+1, col+1), then return the minimum of these sums plus the current element. While correct, this method is exponentially slow (O(3^n)) because it recomputes the same subproblems multiple times.

The optimal approach uses dynamic programming (DP). The key insight is that the minimum falling path sum to a given cell depends only on the minimum sums to the three cells directly above it. We can build a DP matrix where each cell stores the minimum falling path sum ending at that cell. By iterating row by row, we can update each cell based on the values in the previous row. This reduces the time complexity to O(n^2) because each cell is visited once, and the space complexity can be O(n^2) or optimized to O(n) using a single array to store the previous row.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) O(n) Recursively explore all paths
Optimal (DP) O(n^2) O(n^2) or O(n) Store min path sum up to each cell

Algorithm Walkthrough

  1. Initialize a DP matrix dp of the same size as matrix and copy the first row from matrix since the minimum path sum to reach any cell in the first row is the value itself.
  2. Iterate over each row i from 1 to n-1.
  3. For each column j in row i, calculate the minimum path sum to reach (i, j) as matrix[i][j] + min(dp[i-1][j], dp[i-1][j-1] if j>0 else inf, dp[i-1][j+1] if j<n-1 else inf).
  4. After filling the DP matrix, the minimum falling path sum is the smallest value in the last row of dp.
  5. Return this minimum value.

Why it works: At each step, the algorithm guarantees that dp[i][j] stores the minimum path sum to reach that cell, which ensures that by the time we reach the last row, we have considered all possible paths efficiently. This is a standard bottom-up dynamic programming technique that leverages overlapping subproblems.

Python Solution

from typing import List

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        if n == 1:
            return matrix[0][0]
        
        dp = [row[:] for row in matrix]
        
        for i in range(1, n):
            for j in range(n):
                left = dp[i-1][j-1] if j > 0 else float('inf')
                up = dp[i-1][j]
                right = dp[i-1][j+1] if j < n-1 else float('inf')
                dp[i][j] += min(left, up, right)
        
        return min(dp[-1])

This implementation first handles the edge case where the matrix is 1x1. The DP matrix is initialized as a copy of matrix. For each cell (i, j) starting from the second row, the minimum sum path to reach that cell is computed by considering the three potential predecessors. The final answer is obtained by finding the minimum value in the last row.

Go Solution

import "math"

func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    if n == 1 {
        return matrix[0][0]
    }
    
    dp := make([][]int, n)
    for i := range matrix {
        dp[i] = make([]int, n)
        copy(dp[i], matrix[i])
    }
    
    for i := 1; i < n; i++ {
        for j := 0; j < n; j++ {
            left, up, right := math.MaxInt, dp[i-1][j], math.MaxInt
            if j > 0 {
                left = dp[i-1][j-1]
            }
            if j < n-1 {
                right = dp[i-1][j+1]
            }
            dp[i][j] += min(left, up, right)
        }
    }
    
    minVal := dp[n-1][0]
    for _, val := range dp[n-1] {
        if val < minVal {
            minVal = val
        }
    }
    return minVal
}

func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

The Go version mirrors the Python implementation. It initializes a DP matrix as a copy of matrix and iteratively updates each cell based on the three potential predecessors. The min helper function selects the minimum among three integers, and math.MaxInt represents infinity for edge cases.

Worked Examples

Example 1

Matrix:

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

Step by step DP:

i\j 0 1 2
0 2 1 3
1 2+6=8 min(2,1,3)+5=6 1+4=5? Wait recalc 
Row 1:
dp[1][0] = 6+min(2,inf,1)=6+1=7
dp[1][1] = 5+min(2,1,3)=5+1=6
dp[1][2] = 4+min(1,3,inf)=4+1=5
Row 2:
dp[2][0] = 7+min(7,inf,6)=7+6=13
dp[2][1] = 8+min(7,6,5)=8+5=13
dp[2][2] = 9+min(6,5,inf)=9+5=14

Minimum in last row: min(13,13,14)=13.

Example 2

Matrix:

[[-19,57],
 [-40,-5]]

Step by step DP:

i\j 0 1
0 -19 57
1 -40+min(-19,inf)=-59 -5+min(-19,57)=-24

Minimum in last row: -59.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We iterate through each cell of the matrix exactly once, computing the min of three values.
Space O(n^2) The DP matrix duplicates the input matrix. Can be reduced to O(n) by keeping only the previous row.

The time complexity is quadratic because we must consider each cell in each row. Space complexity is initially quadratic, but since each row depends only on the previous row, we could optimize it to a single array of size n.

Test Cases

# Provided examples
assert Solution().minFallingPathSum([[2,1,3],[6,5,4],[7,8,9]]) == 13  # example 1
assert Solution().minFallingPathSum([[-19,57],[-40,-5]]) == -59       # example 2

# Single row
assert Solution().minFallingPathSum([[42]]) == 42  # edge case 1x1

# All negative numbers
assert Solution().minFallingPathSum([[-1,-2],[-3,-4]]) == -6  # minimal path sum -1->-3

# Minimum path along the edges
assert Solution().minFallingPathSum([[1,2,3],[4,5,6],[7,8,9]]) == 12  #