931. Minimum Falling Path Sum
Minimum Falling Path Sum (LeetCode 931) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
How to solve Minimum Falling Path Sum
Minimum Falling Path Sum is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.
Work towards the solution in these steps:
- Consider that this problem involves making a sequence of choices with overlapping subproblems, which suggests using Dynamic Programming.
- Think about defining a DP state that represents the minimum falling path sum reaching a particular cell in a given row.
- To compute each state, consider the allowable previous positions from the row above and select the minimum sum among them.
The reference solution runs in O(n^2) time and O(1) space.
The Minimum Falling Path Sum solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Array, Dynamic Programming, Matrix.
Reported in interviews at Amazon.
How to practise Minimum Falling Path Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(1) space.
Open Minimum Falling Path Sum in the code editor, or read the Minimum Falling Path Sum editorial for a worked solution with its approach and complexity analysis.
Where Minimum Falling Path Sum sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 2D Array (Unique Paths on Grid) subpattern
- The full DSA patterns sheet
Problems related to Minimum Falling Path Sum
Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:
- Count Square Submatrices with All Ones — Medium, same subpattern
- Interleaving String — Medium, same subpattern
- Longest Increasing Path in a Matrix — Hard, same subpattern
- Maximal Square — Medium, same subpattern
- Minimum Path Sum — Medium, same subpattern
- Triangle — Medium, same subpattern
Minimum Falling Path Sum FAQ
What is the LeetCode number of Minimum Falling Path Sum?
Minimum Falling Path Sum is LeetCode problem 931, rated Medium.
What pattern is used to solve Minimum Falling Path Sum?
Minimum Falling Path Sum is a Unique Paths on Grid problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
What is the time complexity of Minimum Falling Path Sum?
The reference solution runs in O(n^2) time and O(1) space.
Which companies ask Minimum Falling Path Sum?
Minimum Falling Path Sum has been reported in interviews at Amazon.