Minimum Falling Path Sum

Med

#0885Time: O(n * 3^n). For each of the n starting cells in the first row, we explore a ternary tree of depth n, leading to an exponential number of computations.Space: O(n), where n is the number of rows. This space is used by the recursion stack.2 companies

Patterns

Dynamic Programming

Data structures

Array Matrix

Companies

Intuit Dream11

Prompt

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

Approaches

5 approaches with complexity analysis and trade-offs.

This approach explores all possible falling paths starting from each cell in the first row and recursively calculates the sum for each path. The minimum sum found among all paths is the result. It's a straightforward translation of the problem definition into a recursive structure.

Algorithm

1. The main function initializes a variable minSum to Integer.MAX_VALUE.
1. It then iterates through each column j of the first row (from 0 to n-1).
1. For each starting cell (0, j), it calls a recursive helper function, findMinPath(0, j, matrix), which is designed to find the minimum falling path sum starting from that cell.
1. The minSum is updated with the minimum of its current value and the value returned by the recursive call.
1. The findMinPath(row, col, matrix) helper function works as follows:
- a. It first checks if the column col is out of bounds (< 0 or >= n). If so, it returns Integer.MAX_VALUE to ensure this path is not chosen.
- b. It checks for the base case: if row is the last row (n-1), it returns the value of the current cell, matrix[row][col], as the path ends here.
- c. If it's not the base case, it makes three recursive calls for the cells in the next row: (row + 1, col - 1), (row + 1, col), and (row + 1, col + 1).
- d. It returns the sum of the current cell's value (matrix[row][col]) and the minimum value returned by the three recursive calls.
1. After the loop in the main function completes, minSum holds the minimum falling path sum, which is then returned.

Walkthrough

We define a recursive function, let's call it findMinPath(row, col), that calculates the minimum sum of a falling path starting from the cell (row, col).

The base case for the recursion is when we reach the last row (row == n-1). In this case, the function simply returns the value of the cell matrix[row][col].

For any other cell (row, col), the function calculates its path sum by adding matrix[row][col] to the minimum of the path sums starting from the three possible next cells in the row below: (row+1, col-1), (row+1, col), and (row+1, col+1). We must handle boundary conditions for the columns to ensure we don't go out of bounds.

The main function will call this recursive function for every cell in the first row ((0, 0), (0, 1), ..., (0, n-1)) and return the minimum value among these calls. This method is highly inefficient because it recomputes the minimum path sums for the same cells multiple times.

1class Solution {2    public int minFallingPathSum(int[][] matrix) {3        int n = matrix.length;4        if (n == 0) {5            return 0;6        }7        int minSum = Integer.MAX_VALUE;8        for (int j = 0; j < n; j++) {9            minSum = Math.min(minSum, findMinPath(0, j, matrix));10        }11        return minSum;12    }13 14    private int findMinPath(int row, int col, int[][] matrix) {15        int n = matrix.length;16        // Boundary checks for columns17        if (col < 0 || col >= n) {18            return Integer.MAX_VALUE;19        }20        // Base case: last row21        if (row == n - 1) {22            return matrix[row][col];23        }24 25        // Recursive step26        int left = findMinPath(row + 1, col - 1, matrix);27        int middle = findMinPath(row + 1, col, matrix);28        int right = findMinPath(row + 1, col + 1, matrix);29 30        return matrix[row][col] + Math.min(left, Math.min(middle, right));31    }32}

Complexity

Time

O(n * 3^n). For each of the n starting cells in the first row, we explore a ternary tree of depth n, leading to an exponential number of computations.

Space

O(n), where n is the number of rows. This space is used by the recursion stack.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem's recursive nature.

Cons

Extremely inefficient due to a large number of redundant calculations.
Will result in a 'Time Limit Exceeded' (TLE) error for larger values of n (e.g., n > 20).

This approach improves upon the brute-force recursion by using a memoization table (a 2D array) to store the results of subproblems that have already been solved. This is a top-down dynamic programming technique that avoids redundant computations by looking up previously computed values.

Algorithm

1. Create a memoization table, memo, of the same size as the input matrix and initialize all its cells with a sentinel value (e.g., Integer.MAX_VALUE) to indicate that they haven't been computed.
1. The main function iterates through each starting column j in the first row.
1. It calls a helper recursive function findMinPath(0, j, matrix, memo) and keeps track of the minimum sum found.
1. The findMinPath(row, col, matrix, memo) function is modified from the brute-force version:
- a. It first checks if the result for (row, col) is already stored in memo[row][col]. If memo[row][col] is not the sentinel value, it returns the stored result immediately.
- b. If the result is not memoized, it proceeds with the same logic as the brute-force approach: handle boundaries, check for the base case (last row), and make recursive calls for the three children cells.
- c. After computing the result, it stores it in memo[row][col] before returning it.
1. The final result is the minimum value found after checking all starting positions in the first row.

Walkthrough

We use a 2D array, memo, of the same dimensions as the input matrix, to store the minimum falling path sum starting from each cell (row, col). We initialize the memo table with a special value (e.g., Integer.MAX_VALUE) to indicate that a state has not been computed yet.

The recursive function findMinPath(row, col) is modified:

Before computing the result, it first checks if memo[row][col] already contains a computed value. If so, it returns the stored value immediately.
If not, it computes the result recursively, just like in the brute-force approach.
Before returning, it stores the computed result in memo[row][col] for future use.

This technique ensures that the minimum path sum for each cell (row, col) is calculated only once, drastically reducing the time complexity.

1class Solution {2    public int minFallingPathSum(int[][] matrix) {3        int n = matrix.length;4        if (n == 0) {5            return 0;6        }7        int[][] memo = new int[n][n];8        for (int[] row : memo) {9            java.util.Arrays.fill(row, Integer.MAX_VALUE);10        }11 12        int minSum = Integer.MAX_VALUE;13        for (int j = 0; j < n; j++) {14            minSum = Math.min(minSum, findMinPath(0, j, matrix, memo));15        }16        return minSum;17    }18 19    private int findMinPath(int row, int col, int[][] matrix, int[][] memo) {20        int n = matrix.length;21        if (col < 0 || col >= n) {22            return Integer.MAX_VALUE;23        }24        if (row == n - 1) {25            return matrix[row][col];26        }27        if (memo[row][col] != Integer.MAX_VALUE) {28            return memo[row][col];29        }30 31        int left = findMinPath(row + 1, col - 1, matrix, memo);32        int middle = findMinPath(row + 1, col, matrix, memo);33        int right = findMinPath(row + 1, col + 1, matrix, memo);34 35        memo[row][col] = matrix[row][col] + Math.min(left, Math.min(middle, right));36        return memo[row][col];37    }38}

Complexity

Time

O(n^2). Each of the `n*n` subproblems (states) is solved only once. The work for each state is constant.

Space

O(n^2). This is dominated by the `n x n` memoization table. The recursion stack also uses O(n) space.

Trade-offs

Pros

Drastically more efficient than brute-force, with a polynomial time complexity.
Guaranteed to pass within typical time limits.
Maintains the recursive structure which can be intuitive.

Cons

Requires O(n^2) extra space for the memoization table, which can be substantial for large n.

This approach uses an iterative, bottom-up method to solve the problem. It builds the solution from the base cases (the first row) upwards. A 2D DP table is used to store the minimum falling path sum ending at each cell, effectively eliminating recursion.

Algorithm

1. Create a 2D DP table, dp, of size n x n.
1. Initialize the first row of the dp table by copying the values from the first row of the input matrix. This is our base case: dp[0][j] = matrix[0][j].
1. Iterate through the matrix row by row, starting from the second row (i = 1 to n-1).
1. For each cell (i, j) in the current row, calculate its DP value using the recurrence relation: dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]).
1. Handle boundary conditions for columns. For j=0, the 'left' option is not available. For j=n-1, the 'right' option is not available. Use a large value like Integer.MAX_VALUE for out-of-bounds predecessors.
1. After filling the entire dp table, the last row dp[n-1] will contain the minimum falling path sums ending at each column j.
1. Find the minimum value in the last row of the dp table and return it as the final answer.

Walkthrough

We create a 2D array dp of the same size as the matrix. dp[i][j] will store the minimum sum of a falling path that ends at cell (i, j).

The base case is the first row. We initialize the first row of our dp table with the values from the first row of the matrix: dp[0][j] = matrix[0][j].

We then iterate from the second row (i = 1) to the last row (i = n-1). For each cell (i, j), we calculate dp[i][j] based on the values in the previous row of the dp table. The recurrence relation is: dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]).

After filling the entire dp table, the values in the last row dp[n-1] represent the total minimum sums of all falling paths ending at each respective column. The final answer is the minimum value in this last row.

1class Solution {2    public int minFallingPathSum(int[][] matrix) {3        int n = matrix.length;4        if (n == 0) {5            return 0;6        }7        int[][] dp = new int[n][n];8 9        // Initialize the first row of dp table10        for (int j = 0; j < n; j++) {11            dp[0][j] = matrix[0][j];12        }13 14        // Fill the rest of the dp table15        for (int i = 1; i < n; i++) {16            for (int j = 0; j < n; j++) {17                int middle = dp[i - 1][j];18                int left = (j > 0) ? dp[i - 1][j - 1] : Integer.MAX_VALUE;19                int right = (j < n - 1) ? dp[i - 1][j + 1] : Integer.MAX_VALUE;20                dp[i][j] = matrix[i][j] + Math.min(middle, Math.min(left, right));21            }22        }23 24        // Find the minimum sum in the last row25        int minSum = Integer.MAX_VALUE;26        for (int j = 0; j < n; j++) {27            minSum = Math.min(minSum, dp[n - 1][j]);28        }29        return minSum;30    }31}

Complexity

Time

O(n^2) due to the nested loops iterating through the entire matrix once.

Space

O(n^2) for the `dp` table.

Trade-offs

Pros

Avoids recursion and potential stack overflow issues for very deep recursion.
Often slightly faster in practice than memoization due to the absence of recursion overhead.
The iterative logic can be easier to reason about for some.

Cons

Uses O(n^2) extra space, which is the same as memoization and can be improved.

This approach optimizes the space complexity of the tabulation method. By observing that the calculation for the current row's DP values only depends on the values from the immediately preceding row, we can avoid storing the entire 2D DP table. Instead, we only need to keep track of the previous row's results, reducing the space requirement significantly.

Algorithm

1. Create a 1D array, prevRow, of size n.
1. Initialize prevRow with the values from the first row of the matrix.
1. Iterate from the second row of the matrix (i = 1 to n-1).
1. Inside this loop, create another 1D array, currRow, of size n.
1. Iterate through the columns (j = 0 to n-1) of the current row i.
1. For each column j, calculate currRow[j] using the values from prevRow: currRow[j] = matrix[i][j] + min(prevRow[j-1], prevRow[j], prevRow[j+1]), handling column boundaries.
1. After the inner loop (all columns of row i are processed), update prevRow to be currRow for the next iteration (i.e., prevRow = currRow).
1. After the outer loop finishes, prevRow will hold the minimum path sums for the last row.
1. Find and return the minimum value in the prevRow array.

Walkthrough

Instead of a full n x n DP table, we only need to store the DP values for the previous row to compute the current row. We can use a 1D array, let's call it prevRow, of size n.

We initialize prevRow with the values from the first row of the matrix. Then, we iterate from the second row (i = 1) to the last row (i = n-1). In each iteration, we compute a currRow (another 1D array of size n) using the values from prevRow. After computing all values for currRow, we update prevRow to be currRow for the next iteration.

After the outer loop finishes, prevRow will hold the minimum path sums for the last row. The final answer is the minimum value in this prevRow array.

1class Solution {2    public int minFallingPathSum(int[][] matrix) {3        int n = matrix.length;4        if (n == 0) {5            return 0;6        }7 8        int[] prevRow = new int[n];9        // Initialize prevRow with the first row of the matrix10        System.arraycopy(matrix[0], 0, prevRow, 0, n);11 12        for (int i = 1; i < n; i++) {13            int[] currRow = new int[n];14            for (int j = 0; j < n; j++) {15                int middle = prevRow[j];16                int left = (j > 0) ? prevRow[j - 1] : Integer.MAX_VALUE;17                int right = (j < n - 1) ? prevRow[j + 1] : Integer.MAX_VALUE;18                currRow[j] = matrix[i][j] + Math.min(middle, Math.min(left, right));19            }20            // Update prevRow for the next iteration21            prevRow = currRow;22        }23 24        // Find the minimum sum in the last row's dp values25        int minSum = Integer.MAX_VALUE;26        for (int val : prevRow) {27            minSum = Math.min(minSum, val);28        }29        return minSum;30    }31}

Complexity

Time

O(n^2). The nested loop structure remains the same as the standard tabulation approach.

Space

O(n). We use two 1D arrays of size `n` to store the DP values for the previous and current rows.

Trade-offs

Pros

Significant space improvement over the standard tabulation and memoization approaches.
Maintains the efficient O(n^2) time complexity.

Cons

Slightly more complex logic to manage two arrays compared to a single 2D DP table.

This is the most space-efficient approach. It builds upon the bottom-up DP logic but cleverly reuses the input matrix itself as the DP table. This eliminates the need for any extra space proportional to the input size, achieving constant extra space complexity.

Algorithm

1. Start iterating from the second row of the matrix (i = 1 to n-1).
1. For each row i, iterate through its columns (j = 0 to n-1).
1. For each cell (i, j), find the minimum path sum from the three possible parent cells in the previous row i-1: matrix[i-1][j-1], matrix[i-1][j], and matrix[i-1][j+1]. Handle boundary conditions for j-1 and j+1.
1. Update the value of the current cell matrix[i][j] by adding this minimum value to it. matrix[i][j] += min_from_previous_row.
1. After the loops complete, the last row of the matrix (matrix[n-1]) will have been updated to contain the minimum falling path sums ending at each respective cell.
1. Iterate through the last row of the modified matrix to find the minimum value.
1. Return this minimum value as the final answer.

Walkthrough

This approach modifies the input matrix in-place to store the DP values. This is possible because when we compute the values for row i, we only need the values from row i-1. Once matrix[i][j] is updated, its original value is no longer needed for any subsequent calculations in this problem.

We start our iteration from the second row (i = 1). For each cell (i, j), we update its value by adding the minimum of the path sums from the cells above it in the previous row. The previous row i-1 already contains the computed minimum path sums up to that row.

The update rule is: matrix[i][j] = matrix[i][j] + min(matrix[i-1][j-1], matrix[i-1][j], matrix[i-1][j+1]), with boundary checks. After iterating through all rows, the last row of the matrix will contain the final minimum sums. The answer is the minimum value in this modified last row.

1class Solution {2    public int minFallingPathSum(int[][] matrix) {3        int n = matrix.length;4        if (n == 0) {5            return 0;6        }7 8        // Iterate from the second row, updating the matrix in-place9        for (int i = 1; i < n; i++) {10            for (int j = 0; j < n; j++) {11                // Get the minimum from the previous row12                int middle = matrix[i - 1][j];13                int left = (j > 0) ? matrix[i - 1][j - 1] : Integer.MAX_VALUE;14                int right = (j < n - 1) ? matrix[i - 1][j + 1] : Integer.MAX_VALUE;15                16                // Update the current cell with the minimum path sum17                matrix[i][j] += Math.min(middle, Math.min(left, right));18            }19        }20 21        // Find the minimum in the last row of the modified matrix22        int minSum = Integer.MAX_VALUE;23        for (int j = 0; j < n; j++) {24            minSum = Math.min(minSum, matrix[n - 1][j]);25        }26        return minSum;27    }28}

Complexity

Time

O(n^2). We traverse the matrix once to update the values.

Space

O(1). No extra space proportional to the input size is used. We only use a few variables for loops and storing temporary values.

Trade-offs

Pros

Optimal space complexity.
Very efficient in both time and space.
Code is concise and clean.

Cons

This approach modifies the input matrix, which might be undesirable if the original matrix needs to be preserved.

Solutions

Solution

1class Solution {2public3  int minFallingPathSum(int[][] matrix) {4    int n = matrix.length;5    var f = new int[n];6    for (var row : matrix) {7      var g = f.clone();8      for (int j = 0; j < n; ++j) {9        if (j > 0) {10          g[j] = Math.min(g[j], f[j - 1]);11        }12        if (j + 1 < n) {13          g[j] = Math.min(g[j], f[j + 1]);14        }15        g[j] += row[j];16      }17      f = g;18    }

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

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int minFallingPathSum(int[][] matrix) {4    int n = matrix.length;5    var f = new int[n];6    for (var row : matrix) {7      var g = f.clone();8      for (int j = 0; j < n; ++j) {9        if (j > 0) {10          g[j] = Math.min(g[j], f[j - 1]);11        }12        if (j + 1 < n) {13          g[j] = Math.min(g[j], f[j + 1]);14        }15        g[j] += row[j];16      }17      f = g;18    }

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

1class Solution:2    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)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.