Minimum Falling Path Sum II solution and explanation
Google
9 more videos on this problem
Minimum Falling Path Sum II - Leetcode 1289 - PythonNeetCodeIO · 31:44 · 10K views
1289. Minimum Falling Path Sum II | LEETCODE HARD | DYNAMIC PROGRAMMING | BITS PILANIcode Explainer · 8:22 · 4K views
1289. Minimum Falling Path Sum II | DP | Greedy | 5 WaysAryan Mittal · 40:09 · 3K views
Leetcode 1289: Minimum Falling Path Sum IIAlgorithms Casts · 11:50 · 1K views
Minimum Falling Path Sum II (LeetCode 1289)(DP HARD) (Optimal Solution)CodeWithARB · 54:56 · 204 views
LeetCode 1289 - Minimum Falling Path Sum II - JavaAlpha-Code · 21:55 · 202 views
LeetCode 1289. Minimum Falling Path Sum II — Without Modifying Input — 24 Lines — O(n^2) / O(n)Garrett Smith · 10:00 · 78 views
Leetcode 1289. Minimum Falling Path Sum II || Dynamic Programming || Memoization|| (26April2024)Shaurya Awasthi · 13:35 · 42 views
Minimum Falling Path Sum II | LeetCode 1289 | Explained 931 | Java Code Tutorial | Developer CoderDeveloper Coder · 16:35 · 34 views
Leetcode 1289. Minimum Falling Path Sum IIFearless Learner · 18:02 · 34 views
The problem
Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.
A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: 13 Explanation: The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] The falling path with the smallest sum is [1,5,7], so the answer is 13.
Example 2:
Input: grid = [[7]] Output: 7
Constraints:
n == grid.length == grid[i].length1 <= n <= 200-99 <= grid[i][j] <= 99
Approach overview
Problem Overview: Given an n x n grid, choose one number from each row such that no two chosen numbers from consecutive rows come from the same column. The goal is to minimize the total sum. This is a classic constrained transition problem in dynamic programming over a matrix.
Approach 1: Dynamic Programming with State Tracking (Time: O(n^2), Space: O(n^2))
Define dp[r][c] as the minimum sum of a falling path that ends at row r and column c. The transition requires picking the minimum value from the previous row except the same column. A naive scan for every column would cost O(n) per state, leading to O(n^3). Instead, track the smallest and second smallest values from the previous row along with their column indices. If the current column differs from the column of the smallest value, use that; otherwise use the second smallest.
This trick removes the inner scan and keeps transitions constant time. Iterate row by row, updating the DP table while maintaining the two minimum values for each row. The algorithm relies on efficient state reuse and works well for grid problems involving column restrictions, a common pattern in array and matrix DP.
Approach 2: Dynamic Programming with Space Optimization (Time: O(n^2), Space: O(n))
The full DP table is unnecessary because each row depends only on the previous one. Store just a single array representing the previous row's DP values. While processing the current row, compute the smallest and second smallest values from the previous array and update a new array for the current row.
After finishing a row, replace the previous array with the current one. This reduces memory usage from O(n^2) to O(n) while preserving the same transition logic and time complexity. The approach is particularly useful when n is large or when implementing the solution in memory-constrained environments.
Recommended for interviews: Interviewers expect the optimized dynamic programming solution using the smallest and second smallest values per row. Showing the straightforward DP idea first demonstrates understanding of the recurrence, but recognizing the min/second-min optimization proves strong problem-solving skills.
Approach 1: Dynamic Programming with State Tracking
This approach uses dynamic programming to keep track of the minimum sum at each position and makes sure no two consecutive rows select a value from the same column. We use a 2D DP array where dp[i][j] represents the minimum path sum to reach element grid[i][j]. Expand on each row by calculating potential path sums from the previous row using existing minimum path sums stored in the DP table.
class Solution:
def minFallingPathSum(self, grid):
n = len(grid)
dp = [row[:] for row in grid]
for i in range(1, n):
for j in range(n):
minPrev = min(dp[i-1][k] for k in range(n) if k != j)
dp[i][j] = grid[i][j] + minPrev
return min(dp[-1])class Solution {
public int minFallingPathSum(int[][] grid) {
int n = grid.length;
int[][] dp = new int[n][n];
for (int j = 0; j < n; j++) dp[0][j] = grid[0][j];
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = Math.min(minPrev, dp[i - 1][k]);
}
dp[i][j] = grid[i][j] + minPrev;
}
}
int minPath = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) minPath = Math.min(minPath, dp[n - 1][j]);
return minPath;
}
}#include <vector>
#include <algorithm>
int minFallingPathSum(std::vector<std::vector<int>>& grid) {
int n = grid.size();
std::vector<std::vector<int>> dp = grid;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = INT_MAX;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = std::min(minPrev, dp[i - 1][k]);
}
dp[i][j] = grid[i][j] + minPrev;
}
}
return *std::min_element(dp[n - 1].begin(), dp[n - 1].end());
}var minFallingPathSum = function(grid) {
const n = grid.length;
const dp = Array.from({ length: n }, (v, i) => [...grid[i]]);
for (let i = 1; i < n; i++) {
for (let j = 0; j < n; j++) {
let minPrev = Infinity;
for (let k = 0; k < n; k++) {
if (k !== j) minPrev = Math.min(minPrev, dp[i-1][k]);
}
dp[i][j] = grid[i][j] + minPrev;
}
}
return Math.min(...dp[n-1]);
};#include <limits.h>
int minFallingPathSum(int** grid, int gridSize, int* gridColSize) {
int n = gridSize;
int dp[n][n];
for (int j = 0; j < n; j++) dp[0][j] = grid[0][j];
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = INT_MAX;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = fmin(minPrev, dp[i - 1][k]);
}
dp[i][j] = grid[i][j] + minPrev;
}
}
int minPath = INT_MAX;
for (int j = 0; j < n; j++) minPath = fmin(minPath, dp[n - 1][j]);
return minPath;
}public class Solution {
public int MinFallingPathSum(int[][] grid) {
int n = grid.Length;
int[][] dp = new int[n][];
for (int i = 0; i < n; i++) {
dp[i] = new int[n];
Array.Copy(grid[i], dp[i], n);
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = Int32.MaxValue;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = Math.Min(minPrev, dp[i-1][k]);
}
dp[i][j] = grid[i][j] + minPrev;
}
}
return dp[n-1].Min();
}
}In Python, we copy the grid into a new DP matrix, iteratively calculating the minimum path sums while disallowing consecutive selection from the same column.
Time Complexity: O(n^3) because we need to calculate the minimum for each non-zero shift.
Space Complexity: O(n^2) for storing intermediate path sums in the DP list.
Approach 2: Dynamic Programming with Space Optimization
This approach enhances space efficiency by using two 1D arrays to store only the last row and the current row values of the DP computations. At each step, we compute the minimum path and store it, minimizing space usage to O(n) instead of O(n^2).
class Solution:
def minFallingPathSum(self, grid):
n = len(grid)
prev = grid[0][:]
for i in range(1, n):
curr = [0] * n
for j in range(n):
minPrev = min(prev[k] for k in range(n) if k != j)
curr[j] = grid[i][j] + minPrev
prev = curr
return min(prev)class Solution {
public int minFallingPathSum(int[][] grid) {
int n = grid.length;
int[] prev = grid[0].clone();
int[] curr = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = Math.min(minPrev, prev[k]);
}
curr[j] = grid[i][j] + minPrev;
}
System.arraycopy(curr, 0, prev, 0, n);
}
return Arrays.stream(prev).min().getAsInt();
}
}#include <vector>
#include <algorithm>
int minFallingPathSum(std::vector<std::vector<int>>& grid) {
int n = grid.size();
std::vector<int> prev = grid[0];
std::vector<int> curr(n);
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = INT_MAX;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = std::min(minPrev, prev[k]);
}
curr[j] = grid[i][j] + minPrev;
}
prev = curr;
}
return *std::min_element(prev.begin(), prev.end());
}var minFallingPathSum = function(grid) {
const n = grid.length;
let prev = [...grid[0]];
for (let i = 1; i < n; i++) {
const curr = new Array(n).fill(Infinity);
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
if (k !== j) {
curr[j] = Math.min(curr[j], grid[i][j] + prev[k]);
}
}
}
prev = curr;
}
return Math.min(...prev);
};#include <limits.h>
#include <string.h>
int minFallingPathSum(int** grid, int gridSize, int* gridColSize) {
int n = gridSize;
int prev[n], curr[n];
memcpy(prev, grid[0], sizeof(int) * n);
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = INT_MAX;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = fmin(minPrev, prev[k]);
}
curr[j] = grid[i][j] + minPrev;
}
memcpy(prev, curr, sizeof(int) * n);
}
int minPath = INT_MAX;
for (int j = 0; j < n; j++) minPath = fmin(minPath, prev[j]);
return minPath;
}public class Solution {
public int MinFallingPathSum(int[][] grid) {
int n = grid.Length;
int[] prev = (int[])grid[0].Clone();
int[] curr = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = Int32.MaxValue;
for (int k = 0; k < n; k++) {
if (k != j) minPrev = Math.Min(minPrev, prev[k]);
}
curr[j] = grid[i][j] + minPrev;
}
Array.Copy(curr, prev, n);
}
return curr.Min();
}
}In Python, this code iteration pattern maintains two arrays, prev and curr, for minimal fall path calculations along shifted columns, reducing space use efficiently to O(n).
Time Complexity: O(n^3) due to looping through matrix positioning and element validation.
Space Complexity: O(n) with arrays limited to current paths handling.
Approach 3: Dynamic Programming
We define f[i][j] to represent the minimum sum of the first i rows, with the last number in the j-th column. The state transition equation is:
$
f[i][j] = min_{k neq j} f[i - 1][k] + grid[i - 1][j]
where k represents the column of the number in the (i - 1)-th row, and the number in the i-th row and j-th column is grid[i - 1][j].
The final answer is the minimum value in f[n].
The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the number of rows in the matrix.
We note that the state f[i][j] only depends on f[i - 1][k], so we can use a rolling array to optimize the space complexity to O(n)$.
function minFallingPathSum(grid: number[][]): number {
const n = grid.length;
const f: number[] = Array(n).fill(0);
for (const row of grid) {
const g = [...row];
for (let i = 0; i < n; ++i) {
let t = Infinity;
for (let j = 0; j < n; ++j) {
if (j !== i) {
t = Math.min(t, f[j]);
}
}
g[i] += t === Infinity ? 0 : t;
}
f.splice(0, n, ...g);
}
return Math.min(...f);
}func minFallingPathSum(grid [][]int) int {
f := make([]int, len(grid))
const inf = math.MaxInt32
for _, row := range grid {
g := slices.Clone(row)
for i := range f {
t := inf
for j := range row {
if j != i {
t = min(t, f[j])
}
}
if t != inf {
g[i] += t
}
}
f = g
}
return slices.Min(f)
}impl Solution {
pub fn min_falling_path_sum(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let mut f = vec![0; n];
let inf = i32::MAX;
for row in grid {
let mut g = row.clone();
for i in 0..n {
let mut t = inf;
for j in 0..n {
if j != i {
t = t.min(f[j]);
}
}
g[i] += if t == inf { 0 } else { t };
}
f = g;
}
*f.iter().min().unwrap()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Tracking | Time Complexity: O(n^3) because we need to calculate the minimum for each non-zero shift. |
| Dynamic Programming with Space Optimization | Time Complexity: O(n^3) due to looping through matrix positioning and element validation. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with State Tracking | O(n^2) | O(n^2) | Clear DP formulation when learning the recurrence or debugging transitions |
| Dynamic Programming with Space Optimization | O(n^2) | O(n) | Preferred approach for interviews or large matrices where memory efficiency matters |
Frequently asked questions
Is Minimum Falling Path Sum II easy or hard?
LeetCode classifies Minimum Falling Path Sum II as a Hard problem. The challenge comes from recognizing how to optimize the DP transition by tracking two minimum values instead of scanning every column.
Minimum Falling Path Sum II Python/Java solution
Python and Java implementations typically maintain an array for the previous row's DP values and compute the smallest and second smallest entries before updating the next row. The algorithm runs in O(n^2) time and can be implemented with either a full DP matrix or a space-optimized single array.
How to solve Minimum Falling Path Sum II in O(n^2)?
Maintain the smallest and second smallest DP values from the previous row along with their column indices. For each column in the current row, use the smallest value unless it came from the same column; otherwise use the second smallest. This removes the need for scanning all columns during transitions.
What is the best approach for Minimum Falling Path Sum II?
The best approach uses dynamic programming with tracking of the smallest and second smallest values from the previous row. This avoids scanning all columns for each transition and reduces the complexity to O(n^2). It processes the grid row by row while ensuring the chosen column differs from the previous row.
Is Minimum Falling Path Sum II asked at Google/Amazon/Meta?
Variants of constrained grid dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. The key skill tested is optimizing DP transitions using tracked minimum values instead of brute-force scanning.
What data structure is used in Minimum Falling Path Sum II?
The solution primarily uses arrays to store dynamic programming states for each row. Additional variables track the smallest and second smallest values from the previous row to enable efficient transitions.
What is the time complexity of Minimum Falling Path Sum II?
The optimized dynamic programming solution runs in O(n^2) time for an n x n grid. Each row is processed once, and transitions are constant time because the smallest and second smallest values from the previous row are precomputed.