Scale Engineer

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
ArrayMatrix
Companies
IntuitDream11

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.

class Solution {    public int minFallingPathSum(int[][] matrix) {        int n = matrix.length;        if (n == 0) {            return 0;        }        int minSum = Integer.MAX_VALUE;        for (int j = 0; j < n; j++) {            minSum = Math.min(minSum, findMinPath(0, j, matrix));        }        return minSum;    }     private int findMinPath(int row, int col, int[][] matrix) {        int n = matrix.length;        // Boundary checks for columns        if (col < 0 || col >= n) {            return Integer.MAX_VALUE;        }        // Base case: last row        if (row == n - 1) {            return matrix[row][col];        }         // Recursive step        int left = findMinPath(row + 1, col - 1, matrix);        int middle = findMinPath(row + 1, col, matrix);        int right = findMinPath(row + 1, col + 1, matrix);         return matrix[row][col] + Math.min(left, Math.min(middle, right));    }}

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).

Solutions

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;    }

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 →

Next problem