Devin's Blog

Minimum Falling Path Sum

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • For top down:
    • Top in this case is the first row, since the top row depends on the 2nd row which depends on the 3rd row etc.
    • On each index, you have the choice of taking one of the indices diagonally left, bottom, or right.
  • For bottom up:
    • Start from the second to last row, in which you use the matrix itself to go about collecting the minimum of the row + 1 (one row down).

Note

You keep getting tripped up by row + 1 being one row down and row - 1 being one row up. Be very careful, or set variables to reduce cognitive load.

Complexity

Runtime

since we must go through cells in an N x N matrix.

Space

since we only ever use the original matrix in the case of bottom up.

Code

Bottom Up

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        for row in reversed(range(n - 1)):
            for col in range(n):
                matrix[row][col] += min(matrix[row + 1][j] for j in [col - 1, col, col + 1] if 0 <= j < n)
        return min(matrix[0])
  • Bottom in this case is the last row

Top Down

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        @cache
        def r(row, col):
            if row >= n or not (0 <= col < n):
                return inf
 
            left_diagonal = r(row + 1, col - 1)
            down = r(row + 1, col)
            right_diagonal = r(row + 1, col + 1)
            srr = min(left_diagonal, down, right_diagonal)
 
            return matrix[row][col] if srr == inf else matrix[row][col] + srr
 
        res = inf
        for c in range(len(matrix[0])):
            res = min(res, r(0, c))
        return res

Notes

Cards

START Basic Front: Minimum Falling Path Sum Back: Collect left diagonal, down, and right diagonal only if the column is within the bounds.

END

References

Graph View