DSA interview question

Minimum Falling Path Sum

Medium · Algorithms · Topics: dynamic programming, matrix

The problem

You're simulating a physics-based puzzle game where a ball drops from the top row of an n x n grid of "energy cost" tiles. From any tile in a row, the ball can fall straight down, or diagonally to the immediately-left or immediately-right column in the row below (never wrapping around edges). The ball starts at any tile in the top row and falls all the way to the bottom row. Your task: compute the minimum total energy cost the ball accumulates over any such falling path.

Example: matrix 2 1 3 6 5 4 7 8 9 Minimum falling path: 1 → 4 → 7 = 12.

Function signature

int minFallingPathSum(vector<vector<int>>& matrix);

Test cases

Input `matrix`	Output	Explanation
`[[2,1,3],[6,5,4],[7,8,9]]`	13	Path: 1 → 4 → 8 (verify: 1+4+8=13)
`[[-19,57],[-40,-5]]`	-59	Path: -19 → -40
`[[1]]`	1	Single cell, trivially the answer
`[[1,2],[3,4]]`	4	Path: 1 → 3
`[[100,100,100],[100,1,100],[100,100,100]]`	101	Path: 100 → 1 → 100 (forced diagonal-diagonal through center)
`[[5,5],[5,5]]`	10	Any path gives the same sum

(Confirm: matrix is always square n x n, n >= 1; values can be negative.)

How interviewers phrase it

"Given a square matrix, find the minimum sum of a path that starts anywhere in the first row and moves to the next row at each step, either straight down or diagonally, ending at the last row."
This is LeetCode 931 (Minimum Falling Path Sum) — a natural follow-up after "Triangle" (LeetCode 120), since the recurrence structure is nearly identical but on a square grid with edge-wrap considerations.
Sometimes phrased as "minimum cost to drop a ball through a grid" or "minimum score path in a matrix with diagonal moves."

Clarifying questions to ask

Confirm the exact set of allowed moves from (row, col): is it (row+1, col-1), (row+1, col), (row+1, col+1) — i.e., straight down or one step diagonally in either direction?
Can the ball start at any column in the top row, not just column 0?
Does the path need to reach a specific target in the bottom row, or can it end at any column?
Is the matrix guaranteed to be square (n x n), or could it be rectangular (which would change nothing structurally, but worth confirming)?
Can matrix values be negative? (Confirms DP is required — no greedy shortcuts possible.)

Follow-ups to expect

"Can you solve it in O(1) extra space (in-place)?"
"What if you also need to output the actual path, not just the sum?"
"How does this differ from the Triangle problem?"
"Can you do this top-down with memoization instead of bottom-up?"
"What if diagonal moves could skip a column (e.g., ±2)?"
"What if the ball can move in any of 8 directions instead of only downward?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview