PPractick

The problem

You're building a route-optimization feature for a delivery-cost estimator. The delivery zones are arranged in a triangular pyramid layout — each level has one more zone than the level above it. Starting from the top zone, a package can move down to one of the two zones directly below it (adjacent) at each step, until it reaches the bottom level. Each zone has a delivery cost. Your task: find the minimum total cost to route the package from the top zone to any zone in the bottom row.

Example: given the triangle 2 3 4 6 5 7 4 1 8 3 the minimum path is 2 → 3 → 5 → 1 = 11.

Function signature

int minimumTotal(vector<vector<int>>& triangle);

Test cases

Input triangle	Output	Explanation
[[2],[3,4],[6,5,7],[4,1,8,3]]	11	Path: 2 → 3 → 5 → 1
[[-10]]	-10	Single row, trivially the answer
[[1],[2,3]]	3	Path: 1 → 2
[[1],[-2,-3]]	-2	Path: 1 → -2 (negative numbers allowed)
[[1],[2,3],[4,5,6]]	7	Path: 1 → 2 → 4
[[5],[9,6],[4,6,8],[0,7,1,5]]	15	Path: 5 → 6 → 4 → 0

(Confirm: triangle can have negative numbers; the number of rows is at least 1, and row i has exactly i+1 elements.)

How interviewers phrase it

• "Given a triangular array of numbers, find the minimum sum path from the top row to the bottom row, where from each element you can move to one of the two adjacent elements in the next row."
• This is directly LeetCode 120 (Triangle) — interviewers may present it verbatim or wrap it in a themed story (delivery costs, elevation/terrain descent, etc.).
• Sometimes phrased in reverse: "find the maximum sum" — same technique, just flip min to max.

Clarifying questions to ask

1. What exactly does "adjacent" mean here — from triangle[i][j], can I move to triangle[i+1][j] and triangle[i+1][j+1]? Confirm this precisely, since off-by-one errors are common.
2. Can the triangle contain negative numbers? (Affects whether greedy approaches would ever be tempting/wrong — DP is needed regardless.)
3. Is the triangle guaranteed non-empty, and is every row i guaranteed to have exactly i+1 elements (well-formed)?
4. Do you want just the minimum sum, or also the actual path taken?
5. Is there a constraint on the number of rows (e.g., up to 200 per LeetCode's constraints) that would rule out exponential solutions?

Follow-ups to expect

1. "Can you do this in O(n) extra space instead of O(n²)?"
2. "Can you do it top-down instead of bottom-up?"
3. "What if you also need to return the actual path, not just the sum?"
4. "What if movement is allowed to any of the row below (not just adjacent)?"
5. "Can this be solved recursively with memoization instead of iterative DP?"
6. "What if we want maximum path sum instead of minimum?"

Related questions

• Kadane's Algorithm Medium
• Print subarray with maximum subarray sum Medium
• Maximum Product Subarray in an Array Medium
• Longest Palindromic Substring Medium
• Climbing stairs Medium
• Frog Jump Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in