Skip to content

931. Minimum Falling Path Sum

Description

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. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

 

Example 1:

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.

Example 2:

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

Solutions

Solution 1: Dynamic Programming (Rolling Array)

Thinking

A falling path may step only to the three adjacent cells in the next row, and \(n\le 100\). Enumerating paths is impossible. The best way to \((i,j)\) depends only on the previous row at \(j-1,j,j+1\). Compute this row by row and roll a one-dimensional array, using \(O(n)\) extra space.

Let \(f[i][j]\) be the minimum falling path sum that ends at row \(i\), column \(j\):

\[ f[i][j] = \textit{matrix}[i][j] + \min \left\{ \begin{aligned} & f[i - 1][j - 1], & j > 0 \\ & f[i - 1][j], & 0 \leq j < n \\ & f[i - 1][j + 1], & j + 1 < n \end{aligned} \right. \]

The answer is \(\min_{0 \leq j < n} f[n - 1][j]\).

\(f[i][j]\) depends only on the previous row, so we keep two arrays \(f\) and \(g\) of length \(n\).

The time complexity is \(O(n^2)\) and the space complexity is \(O(n)\), where \(n\) is the side length of the matrix.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        var f = new int[n];
        for (var row : matrix) {
            var g = f.clone();
            for (int j = 0; j < n; ++j) {
                if (j > 0) {
                    g[j] = Math.min(g[j], f[j - 1]);
                }
                if (j + 1 < n) {
                    g[j] = Math.min(g[j], f[j + 1]);
                }
                g[j] += row[j];
            }
            f = g;
        }
        // return Arrays.stream(f).min().getAsInt();
        int ans = 1 << 30;
        for (int x : f) {
            ans = Math.min(ans, x);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> f(n);
        for (auto& row : matrix) {
            auto g = f;
            for (int j = 0; j < n; ++j) {
                if (j) {
                    g[j] = min(g[j], f[j - 1]);
                }
                if (j + 1 < n) {
                    g[j] = min(g[j], f[j + 1]);
                }
                g[j] += row[j];
            }
            f = move(g);
        }
        return *min_element(f.begin(), f.end());
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    f := make([]int, n)
    for _, row := range matrix {
        g := make([]int, n)
        copy(g, f)
        for j, x := range row {
            if j > 0 {
                g[j] = min(g[j], f[j-1])
            }
            if j+1 < n {
                g[j] = min(g[j], f[j+1])
            }
            g[j] += x
        }
        f = g
    }
    return slices.Min(f)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function minFallingPathSum(matrix: number[][]): number {
    const n = matrix.length;
    const f: number[] = new Array(n).fill(0);
    for (const row of matrix) {
        const g = f.slice();
        for (let j = 0; j < n; ++j) {
            if (j > 0) {
                g[j] = Math.min(g[j], f[j - 1]);
            }
            if (j + 1 < n) {
                g[j] = Math.min(g[j], f[j + 1]);
            }
            g[j] += row[j];
        }
        f.splice(0, n, ...g);
    }
    return Math.min(...f);
}

Comments