How do you solve Triangle on LeetCode?

Triangle (LeetCode #120) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Dynamic programming allows us to build solutions incrementally.

What is the brute force solution for Triangle?

The brute force approach for Triangle is Brute Force, with O(n²) time complexity and O(n) space complexity. In the brute force approach, we explore all possible paths from the top of the triangle to the bottom. This means calculating the sum for every possible route and then selecting the minimum sum. While this is straightforward, it can be very inefficient due to the exponential number of paths. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Triangle?

Triangle uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Greedy Algorithms.

What are the interview tips for Triangle?

Explain your thought process clearly while coding. Don't forget to discuss time and space complexity. Practice dry runs of your solution to ensure correctness.

What are common mistakes when solving Triangle?

Not considering the base case for recursion. Failing to update the triangle in place for the optimal solution.

#120

Triangle

Medium

ArrayDynamic ProgrammingDynamic ProgrammingGreedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(n)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution uses dynamic programming to build the minimum path sum from the bottom of the triangle to the top. By modifying the triangle in place, we can keep track of the minimum sums without using extra space, achieving an efficient solution.

⚙️

Algorithm

3 steps

1Step 1: Start from the second last row of the triangle and move upwards.
2Step 2: For each element, update it to be the sum of itself and the minimum of the two adjacent elements in the row below.
3Step 3: The top element will contain the minimum path sum after processing all rows.

solution.py5 lines

1def minimumTotal(triangle):
2    for row in range(len(triangle) - 2, -1, -1):
3        for col in range(len(triangle[row])):
4            triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])
5    return triangle[0][0]

ℹ

Complexity note: The time complexity remains O(n²) as we still visit each element, but the space complexity is O(1) since we modify the triangle in place.

1Dynamic programming allows us to build solutions incrementally.
2In-place updates can save space and improve efficiency.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.