120. Triangle
Problem Description
Given a triangle
represented as a list of lists where each element represents a level in the triangle, we need to find the minimum path sum
from the top to the bottom. On each level, you start on the element you arrived at from the level above and have two choices: move down to the next level's adjacent element that's either directly below or below to the right (index i
or index i + 1
). The goal is to determine the minimum sum achievable by following these rules from the top to the bottom of the triangle.
Intuition
The approach to solving this problem is based on [dynamic programming](/problems/dynamic_programming_intro)
, which involves breaking down a complex problem into simpler subproblems and solving each only once, storing their solutions – usually in an array.
The intuition behind this solution comes from the realization that the path to reach an element in the triangle depends only on the elements from the previous level that are directly above and to the left, or directly above and to the right. Thus, instead of looking at the problem from top to bottom, we reverse the problem and look from bottom to top.
We use a bottom-up approach, starting from the second-to-last row and moving upward. For each element on the current row, we calculate the minimum path sum to reach it by taking the minimum of the two possible sums from the elements directly below it and adding the current element's value.
The dp
array (short for dynamic programming array) keeps track of these minimum sums. By updating dp
from the bottom row to the top, we ensure that dp[0]
will eventually contain the minimum path sum to reach the top element of the triangle.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution utilizes dynamic programming which significantly reduces the complexity by avoiding the repeated computation of subproblems. The key here is to realize that a bottom-up approach allows us to compute the minimum path sum for each level using the information from the level below it.
-
Data Structures:
We use a single-dimensional arraydp
of sizen + 1
, wheren
is the number of rows in the triangle. The array is initialized with zeroes. This array will store the cumulative minimum path sums for each position of the current level, which will be updated as we iterate through the triangle from the bottom. -
Algorithm:
- We start iterating from the second-to-last row of the
triangle
because the last row's values are the base case for ourdp
array. - For each row
i
, we iterate through its elements, wherej
is the position of the element within the row. - We update the
dp[j]
with the minimum from the two adjacent "child" positions in the row below (dp[j]
anddp[j + 1]
since they are the potential ways to reachdp[j]
) plus the current element's valuetriangle[i][j]
. This update rule reflects the rule of the problem that you can only move toi
ori + 1
when proceeding to the next row.
By continuously updating
dp
in this manner, by the time we reach the first row (i = 0
),dp[0]
will have the minimum path sum to reach the top of the triangle. - We start iterating from the second-to-last row of the
-
Iteration Order:
- We iterate the rows in reverse (
range(n - 1, -1, -1)
), which means we start from the bottom of the triangle and move upwards. - For each row, we iterate through all its elements (
range(i + 1)
), wherei
represents the current row index.
- We iterate the rows in reverse (
The pattern used in the algorithm ensures that dp[j]
always contains the minimum path ending at position j
of the previous row. Therefore, after processing the top row of the triangle, dp[0]
yields the overall minimum path sum from top to bottom.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small triangle as an example to illustrate the solution approach:
1 [2], 2 [3, 4], 3 [6, 5, 7], 4[4, 1, 8, 3]
We want to find the minimum path sum from the top to the bottom by moving to adjacent numbers on the row below.
Applying the Solution Approach:
-
Initialize a
dp
array with zeros. In this case, since we have 4 rows, the size ofdp
will be4 + 1 = 5
. Thus,dp = [0, 0, 0, 0, 0]
. -
Start from the second-to-last row and iterate up, updating the
dp
array:
-
Begin with the bottom row
[4, 1, 8, 3]
, since it will serve as the base case. We don't make any changes todp
as the bottom row's values are the starting minimums. -
Move to the next row
[6, 5, 7]
. We examine each element to determine the minimum path sum from that position:- For
6
at index0
, the minimum path is6 + min(dp[0], dp[1]) => 6 + min(4, 1) = 7
. - For
5
at index1
, the minimum path is5 + min(dp[1], dp[2]) => 5 + min(1, 8) = 6
. - For
7
at index2
, the minimum path is7 + min(dp[2], dp[3]) => 7 + min(8, 3) = 10
. - Now
dp
is updated to[7, 6, 10, 0, 0]
.
- For
-
Move to the next row
[3, 4]
:- For
3
at index0
, the minimum path is3 + min(dp[0], dp[1]) => 3 + min(7, 6) = 9
. - For
4
at index1
, the minimum path is4 + min(dp[1], dp[2]) => 4 + min(6, 10) = 10
. - Update
dp
to[9, 10, 0, 0, 0]
.
- For
-
Finally, we move to the top row
[2]
:- For
2
at index0
, the minimum path is2 + min(dp[0], dp[1]) => 2 + min(9, 10) = 11
. - Update
dp
to[11, 0, 0, 0, 0]
.
- For
- By the end of the iteration,
dp[0]
contains the minimum path sum which is11
. This is the answer we were looking for – the minimum path sum from the top to the bottom of the triangle.
In this example, the minimum path from top to bottom is 2 → 3 → 5 → 1, which sums to 11.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minimumTotal(self, triangle: List[List[int]]) -> int:
5 # Get the number of rows in the triangle
6 num_rows = len(triangle)
7
8 # Initialize a DP array with an extra space to avoid index out of range
9 # This DP array will hold the minimum paths sum from the bottom to the top
10 min_path_sum = [0] * (num_rows + 1)
11
12 # Start from the second to last row of the triangle and move upwards
13 for row in range(num_rows - 1, -1, -1):
14 # For each cell in the row, calculate the minimum path sum to reach that cell
15 for col in range(row + 1):
16 # The minimum path sum for the current cell is the minimum of the path sums
17 # of the two cells directly below it in the triangle plus the cell's value
18 min_path_sum[col] = min(min_path_sum[col], min_path_sum[col + 1]) + triangle[row][col]
19
20 # After updating the whole DP array, the minimum path sum starting from the top
21 # will be in the first cell of the DP array
22 return min_path_sum[0]
23
1class Solution {
2 public int minimumTotal(List<List<Integer>> triangle) {
3 // Get the size of the triangle, which is also the height of the triangle
4 int height = triangle.size();
5 // Create a DP array of size 'height + 1' for bottom-up calculation
6 // This extra space is used to avoid index out of bounds and simplifies calculations
7 int[] dp = new int[height + 1];
8
9 // Start from the second last row of the triangle and move upwards
10 for (int layer = height - 1; layer >= 0; --layer) {
11 // Iterate through all the elements in the current layer
12 for (int index = 0; index <= layer; ++index) {
13 // Calculate the minimum path sum for position 'index' on the current layer
14 // The sum consists of the current element at (layer, index) and the minimum sum of the two adjacent numbers in the layer below
15 dp[index] = Math.min(dp[index], dp[index + 1]) + triangle.get(layer).get(index);
16 }
17 }
18 // The top element of the DP array now contains the minimum path sum for the whole triangle
19 return dp[0];
20 }
21}
22
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int minimumTotal(vector<vector<int>>& triangle) {
7 // Get the depth of the triangle
8 int depth = triangle.size();
9
10 // 'minPathSums' will store the minimum path sum from bottom to top
11 vector<int> minPathSums(depth + 1, 0);
12
13 // Start from the bottom of the triangle and move upwards
14 for (int row = depth - 1; row >= 0; --row) {
15 // Traverse each element of the current row
16 for (int col = 0; col <= row; ++col) {
17 // For each position, calculate the minimum path sum by taking the lesser of the two
18 // adjacent values in the row directly below, and add the current triangle value.
19 // This updates 'minPathSums' in-place for the current row.
20 minPathSums[col] = min(minPathSums[col], minPathSums[col + 1]) + triangle[row][col];
21 }
22 }
23
24 // The top of 'minPathSums' now contains the minimum path sum for the entire triangle
25 return minPathSums[0];
26 }
27};
28
1// Function to find the minimum path sum from top to bottom of a triangle
2function minimumTotal(triangle: number[][]): number {
3 // Get the size of the triangle which is the length of the outer array
4 const triangleSize = triangle.length;
5
6 // Start from the second-to-last row of the triangle and move upwards
7 for (let row = triangleSize - 2; row >= 0; row--) {
8 // Iterate over each element of the current row
9 for (let col = 0; col <= row; col++) {
10 // Update the current element by adding the smaller of the two adjacent numbers from the row below
11 triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]);
12 }
13 }
14
15 // After completion, the top element of the triangle contains the minimum path sum
16 return triangle[0][0];
17}
18
19// The function modifies the input triangle array by storing the sum of the minimum paths at each element,
20// so that the final result is accumulated at the triangle's apex.
21
Time and Space Complexity
The given code implements a dynamic programming approach to solve the triangle problem.
Time complexity:
The time complexity of the algorithm is O(n^2)
, where n
is the number of rows in the triangle. This is because the algorithm consists of two nested loops. The outer loop runs n
times, where n
decreases from the last row to the first row of the triangle. The inner loop runs up to i + 1
times for the i-th
iteration of the outer loop (since each row of the triangle has one more element than the row above it). As we sum up 1 + 2 + ... + n
, which is the series of natural numbers, it leads to the formula n * (n + 1) / 2
. This series is simplified to O(n^2)
.
Space complexity:
The space complexity of the algorithm is O(n)
, where n
is the number of rows in the triangle. This is because the algorithm uses an auxiliary array dp
of size n + 1
. This array is used for storing the minimum path sum from the bottom row to each position (i, j)
in the triangle. As the size of this array does not change with the input size (other than the number of rows n
), the space complexity is linear in the number of rows.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Submit the part you don't understand to our editors. Or join our Discord and ask the community.