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 an array of balloons, each with a number representing coins. When you burst a balloon, you gain coins equal to the product of the balloon's number and its adjacent balloons' numbers. After bursting, the balloon disappears and adjacent balloons become neighbors. Which algorithmic approach guarantees finding the maximum coins you can collect by bursting all balloons in an optimal order?

easy

A. Greedy approach bursting the balloon with the highest number first

B. Sorting balloons and bursting them in ascending order

C. Dynamic programming using interval partitioning and considering the last balloon to burst in each interval

D. Simple recursion trying all burst orders without memoization

Solution

1. Step 1: Understand problem structure

   The problem requires maximizing coins by bursting balloons in an order where each burst depends on adjacent balloons, which changes dynamically.

2. Step 2: Identify suitable algorithm

   Greedy or sorting approaches fail because local choices don't guarantee global optimum. Simple recursion is correct but inefficient. Interval DP solves by considering subproblems defined by intervals and choosing the last balloon to burst in each interval, ensuring optimal substructure.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Interval DP handles overlapping subproblems and changing neighbors [OK]

Hint: Optimal substructure requires interval DP, not greedy [OK]

Common Mistakes:

• Assuming greedy bursting yields max coins
• Trying recursion without memoization
• Ignoring interval-based subproblems

2. You need to find the cheapest cost to travel from a source city to a destination city with at most K stops, given a list of flights with costs. Which algorithmic approach guarantees finding the optimal solution efficiently under these constraints?

easy

A. Greedy algorithm using Dijkstra's shortest path without modification

B. Topological sort followed by single pass relaxation of edges

C. Simple depth-first search exploring all paths without pruning

D. Dynamic programming using a bottom-up approach iterating over stops

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the cheapest flight with at most K stops, which limits path length and requires considering multiple paths.

2. Step 2: Identify suitable algorithm

   Greedy Dijkstra fails because it doesn't limit stops; DFS is exponential; topological sort requires DAG which flights graph may not be. Bottom-up DP iterates over stops and relaxes edges, guaranteeing optimal cost within K stops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bottom-up DP with stops limit ensures optimal solution [OK]

Hint: DP with stops limit ensures optimal cost [OK]

Common Mistakes:

• Using Dijkstra without stop limit
• Trying DFS without pruning
• Assuming DAG for topological sort

3. You are given a grid of non-negative integers representing costs. Starting from the top-left corner, you want to reach the bottom-right corner by moving only down or right, minimizing the total cost along the path. Which algorithmic approach guarantees finding the minimum total cost efficiently?

easy

A. A greedy algorithm that always moves to the adjacent cell with the smallest cost

B. Dynamic programming that builds up solutions from smaller subproblems using a grid-based state

C. Pure brute force recursion exploring all possible paths without memoization

D. Divide and conquer by splitting the grid into halves and solving independently

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing path cost with only down or right moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable algorithmic pattern

   Dynamic programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy which can fail on some grids, brute force which is exponential, or divide and conquer which doesn't handle dependencies well.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP uses subproblem solutions to build the answer bottom-up [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Assuming greedy always works for grid path problems
• Thinking brute force is efficient enough
• Believing divide and conquer applies without overlapping subproblems

4. You need to paint n houses, each with one of k colors. Adjacent houses cannot share the same color. Each color choice has a cost per house. Which algorithmic approach guarantees finding the minimum total painting cost efficiently?

easy

A. Dynamic Programming that tracks minimum costs per house and color, avoiding same-color adjacency

B. Depth-first search exploring all color combinations without memoization

C. Greedy algorithm choosing the cheapest color for each house independently

D. Sorting houses by cost and assigning colors in ascending order

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing total cost with the constraint that no two adjacent houses share the same color.

2. Step 2: Identify suitable algorithm

   Greedy fails because local cheapest choice may cause conflicts later. DFS without memoization is exponential. Sorting houses by cost ignores adjacency constraints. DP tracks costs per house and color, ensuring constraints and optimal substructure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP explicitly handles adjacency and cost minimization [OK]

Hint: DP tracks costs per house and color with adjacency constraints [OK]

Common Mistakes:

• Assuming greedy choice is globally optimal
• Ignoring adjacency constraints in sorting
• Not using memoization in recursion

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