Triangle (Min Path Sum)

📋

Triangle (Min Path Sum)

Edge cases:

</>

IDE

def minimumTotal(triangle: list[list[int]]) -> int:public int minimumTotal(List<List<Integer>> triangle)int minimumTotal(vector<vector<int>>& triangle)function minimumTotal(triangle)

def minimumTotal(triangle: list[list[int]]) -> int:
    # Write your solution here
    pass

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minimumTotal(vector<vector<int>>& triangle) {
    // Write your solution here
    return 0;
}

function minimumTotal(triangle) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 7Greedy approach picking locally minimum adjacent element at each step.✅ Implement DP to consider all paths and choose global minimum, not greedy local minimum.

Wrong: 8Off-by-one error in indexing adjacent elements in DP transitions.✅ Ensure DP uses dp[j] and dp[j+1] correctly for row i+1 when computing dp[j] for row i.

Wrong: 0Incorrect handling of single element triangle or empty input.✅ Add base case to return single element if triangle has only one row.

Wrong: Positive number instead of negativeIncorrect use of max instead of min when combining path sums, or ignoring negative values.✅ Use min() function to combine path sums and handle negative values properly.

Wrong: TLEUsing brute force recursion without memoization or DP.✅ Implement bottom-up or top-down DP with memoization to achieve O(n^2) time complexity.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly.

Watch out for common algorithmic pitfalls like greedy mistakes.

Optimize your solution to run efficiently on large inputs.

t1_01basic

Input{"triangle":[[2],[3,4],[6,5,7],[4,1,8,3]]}

Expected11

⏱ Performance - must finish in 2000ms

The minimum path is 2 → 3 → 5 → 1, which sums to 11.

💡 Think about building the solution from the bottom up.

💡 Use dynamic programming to store minimum path sums for each position.

💡 At each row, dp[i] = triangle[i][j] + min(dp[j], dp[j+1]) from the row below.

Why it failed: Incorrect minimum sum indicates failure to correctly combine subproblems. Fix by ensuring dp updates use min of adjacent lower row values.

✓ Correctly computes minimum path sum using bottom-up DP.

t1_02basic

Input{"triangle":[[-1],[2,3],[1,-1,-3]]}

Expected-1

⏱ Performance - must finish in 2000ms

Minimum path is -1 → 2 → -1 with sum -1.

💡 Negative values can appear; ensure your solution handles them.

💡 DP must correctly choose minimum sums even if negative.

💡 Check that min function is used, not max, when combining paths.

Why it failed: Failing to handle negative values or using max instead of min causes wrong output. Fix by using min() when combining path sums.

✓ Correctly handles negative values and finds minimum path sum.

t2_01edge

Input{"triangle":[[5]]}

Expected5

⏱ Performance - must finish in 2000ms

Single element triangle returns that element as minimum path sum.

💡 Check how your code handles the smallest input size.

💡 Base case: if only one row, return its single element.

💡 Avoid index errors by handling single-row triangle explicitly or via DP.

Why it failed: Code crashes or returns wrong value for single element input. Fix by adding base case for single row or ensuring DP handles it.

✓ Correctly returns single element for single-row triangle.

t2_02edge

Input{"triangle":[[1],[1,1],[1,1,1],[1,1,1,1]]}

Expected4

⏱ Performance - must finish in 2000ms

All elements equal to 1, minimum path sum is number of rows times 1 = 4.

💡 Test uniform values to check if your DP accumulates sums correctly.

💡 Ensure your solution does not mistakenly pick max or sum incorrectly.

💡 Minimum path sum should be sum of any path since all values equal.

Why it failed: Incorrect sum indicates wrong accumulation or path selection. Fix by correctly summing chosen path values.

✓ Correctly sums uniform values along any path.

t2_03edge

Input{"triangle":[[-10000],[-10000,-10000],[-10000,-10000,-10000]]}

Expected-30000

⏱ Performance - must finish in 2000ms

All elements are minimum allowed value; minimum path sum is sum of three -10000 values = -30000.

💡 Check if your solution handles large negative values without overflow.

💡 Use appropriate data types to avoid overflow issues.

💡 Ensure min function works correctly with negative numbers.

Why it failed: Overflow or incorrect handling of negative values causes wrong output. Fix by using int type and min() properly.

✓ Correctly handles large negative values without overflow.

t2_04edge

Input{"triangle":[[0]]}

Expected0

⏱ Performance - must finish in 2000ms

Single element zero tests minimal input with zero value.

💡 Check base case with zero value.

💡 Ensure no extra addition or offset in DP.

💡 Minimum path sum should be zero for single zero element.

Why it failed: Incorrect output for zero single element input. Fix by returning triangle[0][0] when single row.

✓ Correctly returns zero for single zero element.

t3_01corner

Input{"triangle":[[1],[2,3],[1,1,1],[10,1,1,10]]}

Expected5

⏱ Performance - must finish in 2000ms

Greedy approach picking locally minimum adjacent element at each step fails; correct path is 1→2→1→1=5.

💡 Greedy choice at each step may not yield global minimum.

💡 Use DP to consider all paths, not just locally minimal next step.

💡 Store minimum sums from bottom up to avoid greedy trap.

Why it failed: Greedy approach returns 7 (1→3→1→2) instead of 5. Fix by implementing DP to consider all paths.

✓ DP correctly avoids greedy trap and finds global minimum.

t3_02corner

Input{"triangle":[[0],[0,0],[0,0,0],[0,0,0,0]]}

Expected0

⏱ Performance - must finish in 2000ms

All zeros test if solution handles zero values and does not add extra cost.

💡 Check if your solution initializes DP correctly with zeros.

💡 Avoid adding extra values or offsets in DP computation.

💡 Minimum path sum should be zero for all zero triangle.

Why it failed: Incorrect positive sum indicates initialization or addition errors. Fix by initializing DP with triangle values directly.

✓ Correctly computes zero sum for zero-valued triangle.

t3_03corner

Input{"triangle":[[1],[2,3],[3,1,5],[4,1,1,6]]}

Expected7

⏱ Performance - must finish in 2000ms

Off-by-one error test: correct path is 1→2→1→1=7, ensure indices are handled correctly.

💡 Check indexing when moving from row i to i+1, positions j and j+1.

💡 Avoid off-by-one errors in DP transitions.

💡 Verify DP updates use correct adjacent indices.

Why it failed: Off-by-one error causes wrong path sum (e.g., 8). Fix by correctly indexing dp[j] and dp[j+1] in transitions.

✓ Correctly handles indices and computes minimum path sum.

t4_01performance

Input{"triangle":[[0],[0,1],[0,1,2],[0,1,2,3],[0,1,2,3,4],[0,1,2,3,4,5],[0,1,2,3,4,5,6],[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7,8],[0,1,2,3,4,5,6,7,8,9],[0,1,2,3,4,5,6,7,8,9,10],[0,1,2,3,4,5,6,7,8,9,10,11],[0,1,2,3,4,5,6,7,8,9,10,11,12],[0,1,2,3,4,5,6,7,8,9,10,11,12,13],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]]}

Expectednull

⏱ Performance - must finish in 2000ms

Triangle with 200 rows, O(n^2) DP must complete within 2 seconds.

💡 DP solution has O(n^2) time complexity.

💡 Avoid recursion or exponential brute force.

💡 Use bottom-up tabulation with O(n^2) complexity.

Why it failed: Brute force or exponential solutions time out on large input. Fix by implementing O(n^2) DP.

✓ Efficient O(n^2) DP solution passes performance test.

Practice

1. You are given a 2D binary matrix filled with 0's and 1's. The task is to find the largest square containing only 1's and return its area. Which algorithmic approach guarantees an optimal solution with polynomial time complexity?

easy

A. Greedy approach that expands squares from each cell until a zero is found

B. Sorting rows and columns to find the largest continuous block of 1's

C. Depth-First Search exploring all possible squares recursively without memoization

D. Dynamic Programming that builds solutions for smaller squares to find larger ones

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the largest square of 1's, which depends on overlapping subproblems of smaller squares.

2. Step 2: Recognize DP pattern

   Dynamic Programming efficiently computes maximal squares by using previously computed smaller squares, avoiding redundant checks.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP uses subproblem solutions to build larger squares [OK]

Hint: Largest square -> DP using smaller squares [OK]

Common Mistakes:

• Thinking greedy expansion always works
• Confusing DFS with DP
• Assuming sorting helps find squares

2. You are given a convex polygon with n vertices, each vertex having an associated value. The goal is to triangulate the polygon such that the sum of the products of the values of the vertices of each triangle is minimized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Divide and conquer by splitting the polygon into two halves and solving independently

B. A greedy algorithm that always picks the triangle with the smallest immediate product first

C. A simple depth-first search without memoization that explores all triangulations

D. Dynamic programming over intervals that considers all possible triangulations and chooses the minimal cost

Solution

1. Step 1: Understand problem structure

   The problem requires considering all possible triangulations to find the minimal sum of triangle costs, which depends on intervals of vertices.

2. Step 2: Identify suitable algorithm

   Dynamic programming over intervals (interval DP) systematically explores all sub-polygons and stores minimal costs, ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interval DP is the classic approach for polygon triangulation problems [OK]

Hint: Interval DP handles overlapping subproblems optimally [OK]

Common Mistakes:

• Greedy fails due to local minima
• DFS without memoization is exponential
• Divide and conquer ignores polygon connectivity

3. Consider the following bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

4. The following code attempts to solve the Strange Printer problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on inputs like "aba"?

medium

A. Line 18: dp[i][j] = dp[i][j - 1] + 1 assignment

B. Line 13: dp[i][i] = 1 initialization

C. Line 4: compressed.append(c) without checking for duplicates

D. Line 21: if s[k] == s[j] condition

Solution

1. Step 1: Identify compression step

   Line 4 appends every character without checking if it equals the last compressed character, so no compression occurs.

2. Step 2: Understand impact of missing compression

   Without compression, the DP runs on the full string length, causing inefficiency and possibly incorrect merges, especially on inputs like "aba" where compression reduces complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Compression step must skip duplicates to optimize DP [OK]

Hint: Compression must skip consecutive duplicates to avoid TLE and errors [OK]

Common Mistakes:

• Forgetting to compress string before DP

5. Suppose the Cherry Pickup problem is modified so that players can revisit cells multiple times (i.e., cycles allowed), and cherries are replenished after being picked (can be collected multiple times). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use the same 3D DP with memoization but remove the check that prevents revisiting cells.

B. Apply a greedy approach that always moves players to the next cell with the highest cherry count.

C. Use a 4D DP tracking both players' full positions and number of visits per cell to avoid double counting.

D. Switch to a shortest path algorithm like Dijkstra on a state graph representing both players' positions and steps, allowing cycles.

Solution

1. Step 1: Understand the impact of allowing revisits and replenished cherries

   Cycles and replenished cherries mean the problem is no longer acyclic and DP assumptions break down.

2. Step 2: Identify suitable algorithm

   Modeling the problem as a shortest path on a state graph with both players' positions and steps allows handling cycles and repeated cherry collection correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP fails with cycles; shortest path algorithms handle repeated states [OK]

Hint: Cycles break DP; use graph shortest path [OK]

Common Mistakes:

• Removing DP constraints without changing algorithm
• Adding dimensions to DP without handling cycles
• Using greedy which ignores global optimality