120. Triangle
Model: qwen3.5:9b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 46.0%
Problem Breakdown
We are given a triangle represented as an array of arrays (triangle). The goal is to find the minimum path sum from the top (row 0) to any node in the bottom row. We can move down-left or straight-down at each step.
Inputs: A list of lists triangle where triangle[i] has length i + 1.
Outputs: An integer representing the minimum cumulative path sum.
Constraints & Edge Cases:
- Structure: The triangle is guaranteed to be valid (row lengths increase by exactly one).
- Values: Elements can be negative, so we must strictly minimize sums rather than assuming positive integers only.
- Size: Up to 200 rows (), meaning total elements. This fits well within standard time limits for Python if the algorithm is efficient.
- Base Case: A triangle with a single row (Example 2) must return that element’s value immediately without entering any loops meant to process subsequent rows.
Intuition
A brute-force approach would explore every possible path from top to bottom using DFS or BFS. Since there are roughly choices at each step, the number of paths grows exponentially (). For , this is computationally infeasible.
We need Dynamic Programming (DP) because the optimal solution for a cell depends only on the solutions to its immediate children below it. This exhibits optimal substructure.
There are two main DP directions:
- Top-Down: Compute min cost from top down, storing results in a table or memoization map. Requires space for the full triangle structure unless we optimize carefully.
- Bottom-Up: Start at the bottom row and work upwards to the root. This is superior because it naturally aligns with the follow-up requirement of using only
O(n)extra space. We don’t need a recursion stack or memoization table; we can overwrite our state array as we move up, since calculating costs for row depends entirely on values from row .
Approach
We will use Bottom-Up Dynamic Programming with a 1D auxiliary array to satisfy the space constraint.
- Initialize a
dplist of size equal to the last row’s length, populated with the values of the bottom-most row itself (since reaching any node in the bottom row costs just its value). - Iterate upwards from the second-to-last row (
len(triangle) - 2) down to index-1. - For each element at
triangle[i][j], update our DP state: The cost to reach this position is its own value plus the minimum of the two possible paths below it (indicesjandj+1). - Since we are moving up, row has one fewer element than row . We can overwrite the first part of our DP array because index
kin the current level only depends on indiceskandk+1from the previous (lower) level. - After processing all rows up to the top,
dp[0]will contain the minimum path sum for the entire triangle.
Complexity Analysis
- Time Complexity: where is the number of rows. We visit every element in the triangle exactly once during our upward pass. Since there are elements, this scales quadratically with respect to input size.
- Space Complexity: . We use a single list
dpof length equal to the last row’s width (). This satisfies the follow-up constraint strictly without modifying the original input structure (though in-place modification is also possible, using an extra array is cleaner for interview contexts unless specified otherwise).
Solution
def minimumTotal(triangle):
# Handle edge case where triangle has only one row immediately or via loop logic below.
if not triangle:
return 0
n = len(triangle)
# Initialize dp array with the last row values.
# This represents the cost to reach bottom from each position in that specific row.
dp = triangle[-1][:]
# Iterate upwards from second-to-last row down to index -1 (exclusive, so stops at 0).
for i in range(n - 2, -1, -1):
for j in range(len(triangle[i])):
# Update current cell cost + min of two children below it.
# We can update dp[j] directly because we only need values from the row below (dp array).
# The value at triangle[i][j] is added to the minimum path found so far in dp.
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
return dp[0]
# Example usage:
triangle_input = [[2],[3,4],[6,5,7],[4,1,8,3]]
print(minimumTotal(triangle_input)) # Output: 11
Edge Cases Handled
- Single Row Triangle: The loop
range(n - 2, -1, -1)will not execute if . The function returns the single element indp[0], which is correct. - Negative Numbers: Since we strictly use
min(), negative values are handled correctly (e.g., choosing a path with-5over one with2). - Large Values: Python handles arbitrary-precision integers, so overflow beyond standard 32-bit limits does not occur during summation.