Minimum Falling Path Sum
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 or right. Specifically, the next element from position (row, col) will be one of:
(row + 1, col - 1)(row + 1, col)(row + 1, col + 1)
Example 1
2 1 3 6 5 4 7 8 9
Input
matrix = [[2,1,3],[6,5,4],[7,8,9]]Output
13There are two falling paths with a minimum sum of 13.
Example 2
-19 57 -40 -5
Input
matrix = [[-19,57],[-40,-5]]Output
-59The falling path with a minimum sum has total -59.
Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 100
- -100 <= matrix[i][j] <= 100
Asked at 7 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.