What is the optimal approach and complexity for Minimum Falling Path Sum?

One row: each cell takes the smallest of the three old cells above; the old left value is saved in a variable with optimal time complexity O(N^2) and space complexity O(N).

How do you identify the pattern for Minimum Falling Path Sum?

Look for key signals in the prompt: "falling path, down or diagonal" indicates Each step goes to one of three cells in the next row, so a cell has up to three parents above it. The edge columns have only two.; "any cell of the first row" indicates Every falling path starts in row 0, so the first row is the base of the table.; "smallest sum" indicates Each cell keeps the smallest sum of a path that ends there. The answer is the smallest value at the bottom..

Minimum Falling Path Sum

Medium·LeetCode #931 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given an n × n matrix of integers. A falling path starts in any cell of the first row. From each cell, it moves to the next row: straight down, or diagonally down-left, or diagonally down-right. It must stay inside the matrix.

Return the smallest sum of any falling path. The path adds up the cells it visits.

Input

matrix, an n × n grid of integers.

Output

The smallest sum of any falling path through the matrix.

Example 1

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

Output: 13

The path 1 → 5 → 7 (down from the top middle, then down-left) adds up to 13. The path 1 → 4 → 8 also adds up to 13.

Example 2

Input: matrix = [[-19, 57], [-40, -5]]

Output: -59

The best path is -19 → -40, which adds up to -59.

Constraints

• 1 ≤ n ≤ 100
• −100 ≤ matrix[i][j] ≤ 100

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“falling path, down or diagonal”

→ Each step goes to one of three cells in the next row, so a cell has up to three parents above it. The edge columns have only two.

“any cell of the first row”

→ Every falling path starts in row 0, so the first row is the base of the table.

“smallest sum”

→ Each cell keeps the smallest sum of a path that ends there. The answer is the smallest value at the bottom.

Approach Complexity Ladder

Brute Force — try every step from every startO(N · 3^N)O(N)

Recurse down from each first-row cell, trying the cells below that exist, and keep the smallest total

Better — a table of the cheapest path ending at each cellO(N^2)O(N^2)

dp[r][c] = matrix[r][c] + min of the three cells above, filled row by row

Optimal — one row, saving the old left valueO(N^2)O(N)

One row: each cell takes the smallest of the three old cells above; the old left value is saved in a variable

Brute Force Intuition

Let falling(r, c) be the smallest sum of a falling path that starts at (r, c) and reaches the last row. Each cell has up to three children below it, so falling(r, c) = matrix[r][c] + min(...) over the children that exist. Try every start in the first row and keep the smallest.

Recognition rule for this sub-pattern:

dp[r][c] = dp[r−1][c] + dp[r][c−1] (ways) or min(…) + cost (cost).

Remember this · DP — Grid

Trigger

Move only right/down, count paths, minimum path cost, largest square of 1s.

Think

To reach cell (r, c), which cells could I have come from?

Key question

What does dp[r][c] mean, and what are the first row/column?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Grid translate into production architectures and low-level memory mechanics.

LLD Architecture