Is Triangle easy or hard?

Triangle is generally classified as a medium-level problem. The main difficulty is identifying the dynamic programming recurrence and recognizing that each cell depends only on two cells in the next row.

Triangle Python/Java solution

Triangle solutions in Python or Java usually implement bottom-up dynamic programming. Starting from the last row, maintain a DP array and update each position with triangle[row][col] + min(dp[col], dp[col+1]). This produces the minimum path sum at dp[0] after processing all rows.

How to solve Triangle in O(n)?

Triangle cannot be solved in O(n) time because you must inspect every element in the triangle to determine the minimum path. The best achievable time complexity is O(n^2). However, the space complexity can be reduced to O(n) using a bottom-up DP array.

What is the best approach for Triangle?

The best approach is bottom-up dynamic programming with space optimization. Start from the last row and iteratively compute the minimum path sum for the row above using a 1D array. Each update uses min(dp[i], dp[i+1]) from the row below. This runs in O(n^2) time and O(n) space.

Is Triangle asked at Google/Amazon/Meta?

Triangle is a classic dynamic programming problem frequently used in technical interviews. Variants of this problem have appeared in interviews at companies like Amazon, Google, and Meta because it tests DP state transitions, recursion, and space optimization.

What data structure is used in Triangle?

The input is a triangular array structure, and the main technique uses dynamic programming. Solutions typically use either a 2D DP table or a 1D array for space-optimized bottom-up computation.

What is the time complexity of Triangle?

The optimal dynamic programming solutions run in O(n^2) time because every element in the triangle is processed exactly once. If the triangle has n rows, it contains about n^2/2 elements. Both top-down memoization and bottom-up DP share this same time complexity.

Description Solution Video 15:06

120. Triangle

Medium59.9% acceptance11 companies

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10⁴ <= triangle[i][j] <= 10⁴

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Asked at 11 companies

Bloomberg Upstart Walmart Labs Agoda

Google Amazon Microsoft Oracle

Infosys Meta Goldman Sachs

Topics

Array Dynamic Programming

15:06

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minimumTotal(self, triangle: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[2],[3,4],[6,5,7],[4,1,8,3]]

Input

[[-10]]

Your code is saved on this device.Solution