Skip to main content
Talentd

Triangle - Solution & Explanation

MediumArrayDynamic Programming19 min readAsked at: Amazon, Microsoft, Goldman Sachs +8
Practice this problem

Problem Statement

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
  • -104 <= triangle[i][j] <= 104

 

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

Approach Overview

Problem Overview: You are given a triangular array where each row has one more element than the previous row. Starting at the top, move to adjacent numbers in the row directly below and compute the minimum possible path sum from top to bottom.

Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))

This approach treats the triangle as a recursive decision tree. From position (row, col), you can move to (row+1, col) or (row+1, col+1). Use recursion to compute the minimum path sum from the current cell to the bottom, and store results in a memo table so each subproblem is solved once. Memoization eliminates repeated work that appears in naive recursion. This approach is intuitive if you naturally think about exploring paths top‑down and caching results.

Approach 2: Bottom-Up Dynamic Programming (2D DP) (Time: O(n^2), Space: O(n^2))

Instead of exploring paths recursively, build the solution from the bottom row upward. Create a DP table where dp[row][col] stores the minimum path sum from that position to the bottom. For each cell, compute triangle[row][col] + min(dp[row+1][col], dp[row+1][col+1]). Because each value depends only on the row below, iterating from the second-last row to the top fills the table efficiently. This converts the recursive idea into a clean iterative dynamic programming solution.

Approach 3: Bottom-Up Dynamic Programming (Space Optimized) (Time: O(n^2), Space: O(n))

The DP transition only depends on the next row, so a full 2D table is unnecessary. Copy the last row into a 1D array and update it while moving upward through the triangle. For each element, update dp[col] = triangle[row][col] + min(dp[col], dp[col+1]). The array always represents the minimum path sums for the row below the current one. This keeps the same time complexity while reducing memory usage to linear space. The triangle itself is just an array structure, while the optimization relies on recognizing overlapping subproblems typical in dynamic programming.

Recommended for interviews: The bottom-up dynamic programming solution with 1D optimization is what interviewers usually expect. It demonstrates that you understand DP transitions and space optimization. Explaining the top-down memoization version first can help show how you derived the recurrence before converting it into the optimal iterative form.

Approach 1: Dynamic Programming Bottom-Up Approach

In this approach, we'll use dynamic programming (DP) to achieve the solution. We'll start from the bottom of the triangle and minimize the sum path to the top. We'll keep updating the path sum in a DP array as we move to the top row.

The function minimumTotal takes a 2D array representing the triangle and its size and calculates the minimum path sum using a bottom-up DP strategy. We utilize an array dp which holds the path sums for the current row. We iterate from the last row to the first, updating dp till the top.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of rows in the triangle.
Space Complexity: O(n), due to the use of the array dp.

Try this approach in the editor →

Approach 2: Top-Down Dynamic Programming with Memoization

This approach uses a top-down strategy with memoization to store already computed results, avoiding redundant calculations. Each recursive call stores the minimum path sum starting from the current index down to the base of the triangle.

This C code applies a memoization approach, leveraging recursion through dfs to calculate and store intermediate results in memo, exploring both potential paths per cell.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) (due to memoization)
Space Complexity: O(n^2) for memoization storage.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] as the minimum path sum from the bottom of the triangle to position (i, j). Here, position (i, j) refers to the position in row i and column j of the triangle (both indexed from 0). We have the following state transition equation:

$ f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j]

The answer is f[0][0]$.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Dynamic Programming (Space Optimization)

We notice that the state f[i][j] only depends on states f[i + 1][j] and f[i + 1][j + 1]. Therefore, we can use a one-dimensional array instead of a two-dimensional array, reducing the space complexity from O(n^2) to O(n).

The time complexity is O(n^2), and the space complexity is O(n), where n is the number of rows in the triangle.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Bottom-Up Approach

Time Complexity: O(n^2), where n is the number of rows in the triangle.
Space Complexity: O(n), due to the use of the array dp.

Top-Down Dynamic Programming with Memoization

Time Complexity: O(n^2) (due to memoization)
Space Complexity: O(n^2) for memoization storage.

Dynamic Programming—
Dynamic Programming (Space Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Top-Down DP with MemoizationO(n^2)O(n^2)When reasoning recursively about paths and caching overlapping subproblems
Bottom-Up DP (2D table)O(n^2)O(n^2)Clear iterative implementation that mirrors the DP recurrence
Bottom-Up DP (1D optimized)O(n^2)O(n)Preferred approach when minimizing extra memory in interviews

Video Solution

Triangle - Dynamic Programming made Easy - Leetcode 120 • NeetCode • 68,111 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Triangle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays