MediumNo. 0931
Minimum Falling Path Sum — LeetCode 931 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Array, Dynamic Programming, Matrix
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix. A falling path 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.
Example
- 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.
Python solution
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
n = len(matrix)
f = [0] * n
for row in matrix:
g = [0] * n
for j, x in enumerate(row):
l, r = max(0, j - 1), min(n, j + 2)
g[j] = min(f[l:r]) + x
f = g
return min(f)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 931. Minimum Falling Path Sum is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1289 | Minimum Falling Path Sum II | Hard |
| 0063 | Unique Paths II | Medium |
| 0064 | Minimum Path Sum | Medium |
| 0085 | Maximal Rectangle | Hard |
| 0174 | Dungeon Game | Hard |
| 0221 | Maximal Square | Medium |
Frequently asked questions
- How hard is LeetCode 931. Minimum Falling Path Sum?
LeetCode 931. Minimum Falling Path Sum is rated Medium on LeetCode.
- What topics does LeetCode 931. Minimum Falling Path Sum cover?
LeetCode 931. Minimum Falling Path Sum is tagged Array, Dynamic Programming and Matrix on LeetCode.