Minimum Falling Path Sum Python Solution

Tested Python solution for LeetCode 931 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 931, Medium. Topics: Array, Dynamic Programming, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 13 parametrized pytest cases, and a playground notebook:

lcpy gen -n 931   # by problem number
lcpy gen -s minimum_falling_path_sum   # by problem name

​

Problem

<p>Given an <code>n x n</code> array of integers <code>matrix</code>, return <em>the minimum sum of any <strong>falling path</strong> through</em> <code>matrix</code>.</p>

<p>A <strong>falling path</strong> 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 <code>(row, col)</code> will be <code>(row + 1, col - 1)</code>, <code>(row + 1, col)</code>, or <code>(row + 1, col + 1)</code>.</p>

​

Examples

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.

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

​

Constraints

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2)
    # Space: O(n)
    def min_falling_path_sum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        dp = matrix[0][:]
        for row in range(1, n):
            new_dp = [0] * n
            for col in range(n):
                best = dp[col]
                if col > 0:
                    best = min(best, dp[col - 1])
                if col < n - 1:
                    best = min(best, dp[col + 1])
                new_dp[col] = matrix[row][col] + best
            dp = new_dp
        return min(dp)

​

Complexity

Time	Space
O(n^2)	O(n)

​

Tags

NeetCode All.