Skip to main content
Talentd

Minimum Falling Path Sum II - Solution & Explanation

HardArrayDynamic ProgrammingMatrix18 min readAsked at: Meta, Google, Bloomberg
Practice this problem

Problem Statement

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].length
  • 1 <= 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.

This C solution uses an integer array dp to store the minimum path sums, ensuring no same column values from contiguous rows are included by looping to check all columns except the current column.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) where n is the number of rows or columns in the grid.
Space Complexity: O(n^2) for the auxiliary DP array.

Try this approach in the editor →

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

The C solution employs two arrays, prev and curr, to alternate between rows of calculations, minimizing memory use while maintaining previous state information for each row during traversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) because Min operation checks all columns for each column in each row.
Space Complexity: O(n) using two 1D arrays for storing current and previous row states in DP.

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with State Tracking

Time Complexity: O(n^3) where n is the number of rows or columns in the grid.
Space Complexity: O(n^2) for the auxiliary DP array.

Dynamic Programming with Space Optimization

Time Complexity: O(n^3) because Min operation checks all columns for each column in each row.
Space Complexity: O(n) using two 1D arrays for storing current and previous row states in DP.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with State TrackingO(n^2)O(n^2)Clear DP formulation when learning the recurrence or debugging transitions
Dynamic Programming with Space OptimizationO(n^2)O(n)Preferred approach for interviews or large matrices where memory efficiency matters

Video Solution

Minimum Falling Path Sum II - Leetcode 1289 - Python • NeetCodeIO • 10,847 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Falling Path Sum II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Falling Path Sum