931. Minimum Falling Path Sum


Problem Description

In this problem, we have a square (n x n) grid of integers called matrix. A "falling path" can be visualized as a path starting from the first row and moving down to the last row, selecting one integer in each row as part of the sum. At each step, you can move straight down or diagonally down to the left or right. The goal is to find the falling path with the smallest sum of the numbers selected during this process.

Put simply, we're looking for the smallest total we can obtain from top to bottom by choosing numbers according to these rules:

  1. Start at any number in the first row.
  2. Choose a number from the next row that is either directly below, diagonally to the left, or diagonally to the right of the chosen number from the previous row.
  3. Repeat until the last row is reached.
  4. Add up all the numbers selected on this path.
  5. The minimum sum amongst all possible paths is the solution to this problem.

Intuition

The intuition behind the provided solution is to use dynamic programming, which is a way to solve problems by breaking them down into simpler subproblems and building up the solutions to larger problems based on the solutions to the smaller problems.

For this particular problem, we utilize dynamic programming by keeping track of the minimum falling path sum that ends at each element of the current row. We leverage a temporary list f to hold these minimum sums for the previous row as we iterate through each row of the matrix.

As we move from one row to the next, we update our list of minimum sums f so that it always contains the minimum sum up to that point for each possible ending position in the row. At each step, we look at the three possible moves (down, down-left, or down-right) and choose the one that leads to the smallest sum so far.

The key dynamic programming insight here is that the minimum sum at each position in a row only depends on the sums at positions that are either directly above or diagonally above it from the previous row. Therefore, we do not need to remember the entire path to calculate the minimum sum, just the values from the previous row.

At the end of the process, f will contain the minimum sums for the last row, and the smallest number in f will be the minimum sum for the entire matrix.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution follows a dynamic programming approach, which is a strategy for solving complex problems by breaking them down into simpler sub-problems. It efficiently solves problems by storing the sub-problem solutions in a table (usually an array) and using these solutions to construct solutions to bigger problems.

Here's how the algorithm works:

  1. Initialization: We start with a list f of size n (where n is the number of rows and columns of the matrix) that will hold the minimum path sums for each column in the row that we've processed so far. At this point, we consider the first row as our base case, and our initial f list is just the first row of the matrix itself.

  2. Iterating Through Rows: We iterate through each row in the matrix starting from the second row, as the first row is already in our f list.

  3. Updating the Minimum Sums: For each element x in the current row, we:

    • Find the indices l and r which represent the range in the previous row from which we can "fall" to the current element. This range is just below, to the left below, or to the right below the current position.
    • Update the temporary list g to store the new minimum sums. For the current element x, the new minimum sum is calculated by adding x to the minimum of the sums in the range (l, r) from the list f.
    • g[j] = min(f[l:r]) + x
    • The slice f[l:r] gives the sums of the paths that could fall into our current position x.
  4. Copying the Updated Sums: After updating all the elements in the temporary list g for the current row, we copy the contents of g into f so that f now contains the minimum sums for the current row. This process repeats for each row, essentially moving the 'window' of sums down the matrix.

  5. Finding the Result: Once we reach the last row, f will contain the minimum path sums that end in each of the last row's columns. The minimum sum of any falling path through the matrix will then be the smallest value in f.

The dynamic programming pattern used here is known as bottom-up, where the solutions to the smallest sub-problems are computed first and then used to build up the answers to larger problems.

Here is the essence of the code that implements the above algorithm:

1for row in matrix:
2    g = [0] * n
3    for j, x in enumerate(row):
4        l, r = max(0, j - 1), min(n, j + 2)
5        g[j] = min(f[l:r]) + x
6    f = g

This code performs the iterative step where for each number x in the current row, it calculates the minimum path sum ending at that position using the previously stored sums in f, and updates the temporary list g. After processing the row, it replaces f with g, so that f is ready to be used for the next row.

With these steps, the algorithm ensures that by the end, we have computed the minimum sum of all falling paths through the matrix, and we return the smallest value contained in f after processing all the rows.

1return min(f)

This line returns the smallest sum, which is the answer we want.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider a 3x3 matrix:

1matrix = [
2  [2, 1, 3],
3  [4, 5, 1],
4  [7, 8, 9]
5]

We are looking for the minimum falling path sum from the first row to the last.

Following the algorithm steps:

  1. Initialization: Initialize f with the values from the first row.

    f = [2, 1, 3] (representing the path sums including each of the elements in the first row)

  2. Iterating Through Rows: Process the second row [4, 5, 1].

  3. Updating the Minimum Sums: For each element in the second row, calculate the new path sums and temporarily store them in g.

    • When processing 4 (at index 0), the range is f[0:2]. The minimum of f[0:2] is f[1] which is 1.
      1g[0] = 1 + 4 = 5
    • For 5 (at index 1), the range is f[0:3]. The minimum of f[0:3] is again f[1] which is 1.
      1g[1] = 1 + 5 = 6
    • For 1 (at index 2), the range is f[1:3]. The minimum of f[1:3] is f[1] which is 1.
      1g[2] = 1 + 1 = 2

    Now g = [5, 6, 2].

  4. Copying the Updated Sums: Overwrite f with the calculated sums in g.

    f = g = [5, 6, 2]

  5. Process the last row [7, 8, 9] following the same steps:

    • For 7 (index 0): g[0] = min(f[0:2]) + 7 = min(5, 6) + 7 = 5 + 7 = 12
    • For 8 (index 1): g[1] = min(f[0:3]) + 8 = min(5, 6, 2) + 8 = 2 + 8 = 10
    • For 9 (index 2): g[2] = min(f[1:3]) + 9 = min(6, 2) + 9 = 2 + 9 = 11

    After the last row, g = [12, 10, 11] and we update f accordingly.

    f = g = [12, 10, 11]

  6. Finding the Result: The smallest value in f will be the minimum sum of any falling path.

1return min(f)  # Returns 10

The falling path corresponding to the minimum sum is 1 -> 1 -> 8, producing a sum of 10, which is the minimum falling path sum for this matrix.

Solution Implementation

1class Solution:
2    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
3        # Get the size of the matrix
4        size = len(matrix)
5      
6        # Initialize the previous row's minimum falling path sum (top row initially)
7        prev_row_min = [0] * size
8      
9        # Traverse through each row in the matrix
10        for row in matrix:
11            # Initialize the current row's minimum falling path sum
12            current_row_min = [0] * size
13          
14            # For each element in the current row
15            for index, value in enumerate(row):
16                # Determine the valid range to check in previous row
17                # We can pick the current position, or one step left or right
18                left_bound = max(0, index - 1)
19                right_bound = min(size, index + 2)
20              
21                # Calculate the minimum falling path sum for the current element by:
22                # - Finding the min across the valid range from the prev row
23                # - Adding the current element's value to this min
24                current_row_min[index] = min(prev_row_min[left_bound:right_bound]) + value
25          
26            # Update the previous row to current row before moving to the next row
27            prev_row_min = current_row_min
28      
29        # After processing all rows, return the minimum falling path sum
30        return min(prev_row_min)
31
1class Solution {
2  
3    // Function to calculate the minimum falling path sum in a matrix
4    public int minFallingPathSum(int[][] matrix) {
5        int n = matrix.length; // Dimension of the square matrix
6        int[] dpCurrentRow = new int[n]; // Current row dp array
7      
8        // Initialize dp with the first row of matrix.
9        for (int j = 0; j < n; ++j) {
10            dpCurrentRow[j] = matrix[0][j];
11        }
12      
13        // Traverse from second row to the last row
14        for (int rowIdx = 1; rowIdx < n; ++rowIdx) {
15            // Cloning dp array to hold the values for this row calculations
16            int[] dpNextRow = dpCurrentRow.clone();
17          
18            for (int colIdx = 0; colIdx < n; ++colIdx) {
19                // Initialize minimum sum as the value above the current cell
20                int minSumAbove = dpCurrentRow[colIdx];
21              
22                // If not in the first column, consider the upper-left neighbor
23                if (colIdx > 0) {
24                    minSumAbove = Math.min(minSumAbove, dpCurrentRow[colIdx - 1]);
25                }
26                // If not in the last column, consider the upper-right neighbor
27                if (colIdx + 1 < n) {
28                    minSumAbove = Math.min(minSumAbove, dpCurrentRow[colIdx + 1]);
29                }
30              
31                // Update the dp array for the next row with the new minimum
32                dpNextRow[colIdx] = minSumAbove + matrix[rowIdx][colIdx];
33            }
34            // Move to the next row
35            dpCurrentRow = dpNextRow;
36        }
37      
38        // After processing all the rows, find the minimum falling path sum
39        int minFallingPathSum = Integer.MAX_VALUE;
40        for (int x : dpCurrentRow) {
41            minFallingPathSum = Math.min(minFallingPathSum, x);
42        }
43      
44        return minFallingPathSum;
45    }
46  
47}
48
1class Solution {
2public:
3    int minFallingPathSum(vector<vector<int>>& matrix) {
4        int matrixSize = matrix.size(); // Get the size of the matrix
5        vector<int> prevRowCosts(matrixSize); // Initialize a vector to store cost of the previous row
6
7        // Loop over all the rows of the matrix
8        for (auto& row : matrix) {
9            vector<int> currentRowCosts = prevRowCosts; // Copy the previous row costs to the current row (initially)
10
11            // Calculate the current row costs considering the falling path sum from the previous row
12            for (int j = 0; j < matrixSize; ++j) {
13                // Ensure we're not on the first element to avoid going out of bounds
14                if (j > 0) {
15                    currentRowCosts[j] = min(currentRowCosts[j], prevRowCosts[j - 1]); // Take the smaller path from the left diagonal
16                }
17
18                // Ensure we're not on the last element to avoid going out of bounds
19                if (j + 1 < matrixSize) {
20                    currentRowCosts[j] = min(currentRowCosts[j], prevRowCosts[j + 1]); // Take the smaller path from the right diagonal
21                }
22
23                currentRowCosts[j] += row[j]; // Add the current row's cost to the min cost found
24            }
25
26            // Update the previous row costs to be the current row costs for the next iteration
27            prevRowCosts = move(currentRowCosts);
28        }
29
30        // Return the minimum element from the last row, since it contains the min falling path sum for each column
31        return *min_element(prevRowCosts.begin(), prevRowCosts.end());
32    }
33};
34
1/**
2 * Calculates the minimum falling path sum in a square matrix.
3 * A falling path starts at any element in the first row and chooses 
4 * one element from each row. The next row's choice must be in a column 
5 * that is different from the previous row's column by at most one.
6 * 
7 * @param {number[][]} matrix The input square matrix.
8 * @return {number} The minimum falling path sum.
9 */
10function minFallingPathSum(matrix: number[][]): number {
11    const size = matrix.length; // size of the matrix
12    // Initialize the array to store the minimum sum at each position.
13    let currentSums: number[] = new Array(size).fill(0);
14
15    // Iterate over each row of the matrix.
16    for (const row of matrix) {
17        // Copy current sums to temporary array to calculate new sums.
18        let nextSums = [...currentSums];
19
20        // Process each element in the row.
21        for (let col = 0; col < size; ++col) {
22            // If not the first column, take the minimum of the current sum
23            // and the sum from the left neighbor.
24            if (col > 0) {
25                nextSums[col] = Math.min(nextSums[col], currentSums[col - 1]);
26            }
27
28            // If not the last column, take the minimum of the current sum
29            // and the sum from the right neighbor.
30            if (col + 1 < size) {
31                nextSums[col] = Math.min(nextSums[col], currentSums[col + 1]);
32            }
33
34            // Add the current cell's value to the next sum.
35            nextSums[col] += row[col];
36        }
37
38        // Update current sums with the calculated next sums.
39        currentSums = nextSums;
40    }
41
42    // Return the minimum sum found in the last row.
43    return Math.min(...currentSums);
44}
45

Time and Space Complexity

The given Python function minFallingPathSum calculates the minimum falling path sum in a square matrix using dynamic programming.

  • Time Complexity:

    For time complexity, we consider how the algorithm scales with the size of the input matrix, which for our purposes is n x n where n is the length of one side of the matrix.

    The outer loop runs once for each row in the matrix, so it iterates n times. The inner loop runs for each element in a row, also n times. Within the inner loop, we are finding the minimum of a slice of the previous row's data which is a O(1) operation since the slice length is at most 3, regardless of n. Thus, the time complexity is simply the number of times both loops run, multiplied together: O(n) * O(n) = O(n^2).

  • Space Complexity:

    The space complexity is determined by the amount of additional memory the algorithm uses as the size of the input changes.

    In this algorithm, we have two lists, f and g, each of the same size as a row of the matrix, which is n. The contents of f are replaced with the contents of g in each iteration of the outer loop. No other data structures are dependent on the size of the input data. Therefore, the space complexity is O(n) for the list f, plus O(n) for the list g, which still simplifies to O(n) overall.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄