Triangle

Med

#0120Time: O(2^N)Space: O(N)3 companies

Patterns

Dynamic Programming

Data structures

Array

Companies

Agoda Salesforce DE Shaw

Prompt

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?

Approaches

5 approaches with complexity analysis and trade-offs.

The most intuitive way to solve this problem is to think about it recursively. Starting from the top of the triangle at (0, 0), we have two choices at each step: move to the element at index j or j+1 in the row below. We can explore all possible paths from top to bottom, calculate the sum for each path, and then find the minimum among them. This can be implemented with a simple recursive function.

Algorithm

Define a recursive function solve(row, col) that calculates the minimum path sum starting from triangle[row][col].
Base Case: If row is the last row of the triangle (row == triangle.size() - 1), the path sum is just the value of the element itself, so return triangle[row][col].
Recursive Step: For any other cell (row, col), the path must go to either (row + 1, col) or (row + 1, col + 1). Recursively calculate the minimum path sum from these two children nodes:
- path1 = solve(row + 1, col)
- path2 = solve(row + 1, col + 1)
The minimum path sum from (row, col) is the current element's value plus the minimum of the two sub-paths: triangle[row][col] + min(path1, path2).
The final answer is the result of the initial call solve(0, 0).

Walkthrough

This approach defines a recursive function that explores every possible path from the top to the bottom of the triangle. For each node, it makes two recursive calls for its two children in the next row. The function returns the sum of the current node's value and the minimum of the results from its two children's recursive calls. The base case for the recursion is when a path reaches the last row, at which point it returns the value of the node in that row.

1class Solution {2    public int minimumTotal(List<List<Integer>> triangle) {3        return solve(0, 0, triangle);4    }5 6    private int solve(int row, int col, List<List<Integer>> triangle) {7        // Base case: if we are at the last row, return the element's value.8        if (row == triangle.size() - 1) {9            return triangle.get(row).get(col);10        }11 12        // Recursive step: calculate sum for paths going down and down-right.13        int pathDown = solve(row + 1, col, triangle);14        int pathDiagonal = solve(row + 1, col + 1, triangle);15 16        // Return the current element's value plus the minimum of the two paths.17        return triangle.get(row).get(col) + Math.min(pathDown, pathDiagonal);18    }19}

Complexity

Time

O(2^N)

Space

O(N)

Trade-offs

Pros

Simple to conceptualize and implement.
Directly translates the problem definition into code.

Cons

Extremely inefficient due to exponential time complexity.
It recomputes the same subproblems multiple times, leading to a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.

The brute-force recursive approach suffers from re-calculating the minimum path sum for the same nodes multiple times. This is a classic sign of overlapping subproblems, which suggests that dynamic programming can be applied. By storing the results of subproblems in a memoization table (a 2D array), we can avoid redundant computations. This is known as a top-down dynamic programming approach.

Algorithm

Create a 2D array, memo, of the same dimensions as the triangle to store the results of subproblems. Initialize it with a sentinel value (e.g., null).
Define a recursive function solve(row, col, memo).
Base Case: If row is the last row, return triangle[row][col].
Memoization Check: Before computing, check if memo[row][col] has already been calculated. If so, return the stored value.
Recursive Step: If the result is not in the memo table, recursively call the function for the two children nodes:
- path1 = solve(row + 1, col, memo)
- path2 = solve(row + 1, col + 1, memo)
Store and Return: Calculate the minimum path sum triangle[row][col] + min(path1, path2), store it in memo[row][col], and then return it.

Walkthrough

We enhance the recursive solution by adding a cache (memoization table), typically a 2D array memo, to store the minimum path sum for each cell (row, col). Before making recursive calls, we check if the result for the current cell is already in our cache. If it is, we return the cached value directly. Otherwise, we compute the result, store it in the cache, and then return it. This ensures that the minimum path sum for each cell is computed only once.

1class Solution {2    public int minimumTotal(List<List<Integer>> triangle) {3        int n = triangle.size();4        Integer[][] memo = new Integer[n][n];5        return solve(0, 0, triangle, memo);6    }7 8    private int solve(int row, int col, List<List<Integer>> triangle, Integer[][] memo) {9        // Base case10        if (row == triangle.size() - 1) {11            return triangle.get(row).get(col);12        }13 14        // Check if the result is already memoized15        if (memo[row][col] != null) {16            return memo[row][col];17        }18 19        // Recursive step20        int pathDown = solve(row + 1, col, triangle, memo);21        int pathDiagonal = solve(row + 1, col + 1, triangle, memo);22 23        // Memoize the result and return24        memo[row][col] = triangle.get(row).get(col) + Math.min(pathDown, pathDiagonal);25        return memo[row][col];26    }27}

Complexity

Time

O(N^2)

Space

O(N^2)

Trade-offs

Pros

Drastically improves time complexity from exponential to polynomial.
Guarantees that each subproblem is solved only once.
Maintains the logical structure of the recursive solution.

Cons

Requires O(N^2) extra space for the memoization table, which can be substantial for a large triangle.

Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. This is known as tabulation. We start from the destination (the bottom row of the triangle) and work our way up to the start (the top of the triangle). The minimum path sum for a cell is its own value plus the minimum of the path sums of the two cells directly below it.

Algorithm

Create a 2D DP table, dp, of size N x N, where N is the number of rows.
Initialization: Copy the last row of the triangle into the last row of the dp table. This is our base case.
- dp[N-1][j] = triangle[N-1][j] for j from 0 to N-1.
Iteration: Iterate from the second-to-last row (i = N-2) up to the first row (i = 0).
For each row i, iterate through its elements from j = 0 to j = i.
DP Transition: Calculate the value for dp[i][j] using the values from the row below, which have already been computed:
- dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
Result: After the loops complete, the minimum total path sum will be stored in dp[0][0].

Walkthrough

This approach uses a 2D array, dp, to store the minimum path sums. We begin by filling the last row of our dp table with the values from the last row of the input triangle, as the minimum path from any of these cells to the bottom is just the cell's value itself. Then, we iterate upwards, from row N-2 to 0. For each cell (i, j), we calculate its minimum path sum by adding its value to the minimum of the two already-computed path sums in the row below it (dp[i+1][j] and dp[i+1][j+1]). The final answer is the value computed for the top cell, dp[0][0].

1class Solution {2    public int minimumTotal(List<List<Integer>> triangle) {3        int n = triangle.size();4        if (n == 0) return 0;5        6        int[][] dp = new int[n][n];7 8        // Initialize the last row of dp with the last row of the triangle9        for (int j = 0; j < n; j++) {10            dp[n - 1][j] = triangle.get(n - 1).get(j);11        }12 13        // Iterate from the second to last row up to the top14        for (int i = n - 2; i >= 0; i--) {15            for (int j = 0; j <= i; j++) {16                // Calculate the minimum path sum for the current cell17                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);18            }19        }20 21        // The result is at the top of the triangle22        return dp[0][0];23    }24}

Complexity

Time

O(N^2)

Space

O(N^2)

Trade-offs

Pros

Avoids recursion overhead, which can lead to slightly better performance in practice.
Can be more intuitive for problems where the dependency flow is clear.

Cons

Like the memoization approach, it requires O(N^2) extra space.

Observing the bottom-up DP approach, we can see that to compute the minimum path sums for a row i, we only need the results from the row immediately below it, i+1. We don't need any information from rows i+2, i+3, etc. This allows us to optimize the space complexity from O(N^2) to O(N) by using a single 1D array to store the results of the previously processed row.

Algorithm

Create a 1D array, dp, of size N, where N is the number of rows.
Initialization: Initialize dp with the values from the last row of the triangle.
- dp[j] = triangle[N-1][j] for j from 0 to N-1.
Iteration: Iterate from the second-to-last row (i = N-2) up to the first row (i = 0).
For each row i, iterate through its elements from j = 0 to j = i.
DP Transition: Update the dp array in place. The new dp[j] will be the minimum path sum starting from triangle[i][j]. This is calculated using the old dp[j] and dp[j+1] values, which correspond to the minimum paths from the row below.
- dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
Result: After the loops, dp[0] will hold the minimum total path sum.

Walkthrough

This approach follows the same bottom-up logic but uses only a 1D array, dp, of size N (the number of rows). We first initialize this dp array with the values from the last row of the triangle. Then, we iterate from the second-to-last row up to the top. In the inner loop for each row i, we update dp[j] by calculating triangle[i][j] + min(dp[j], dp[j+1]). Here, dp[j] and dp[j+1] still hold the values from the row i+1. By the time we finish iterating through row i, the dp array contains the minimum path sums starting from row i. This process continues until we reach the top, and the final answer is dp[0].

1class Solution {2    public int minimumTotal(List<List<Integer>> triangle) {3        int n = triangle.size();4        int[] dp = new int[n];5 6        // Initialize dp with the last row of the triangle7        for (int j = 0; j < n; j++) {8            dp[j] = triangle.get(n - 1).get(j);9        }10 11        // Iterate from the second to last row up to the top12        for (int i = n - 2; i >= 0; i--) {13            for (int j = 0; j <= i; j++) {14                // Update dp[j] in place. It represents the minimum path sum15                // starting from triangle[i][j].16                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);17            }18        }19 20        // The final result is at dp[0]21        return dp[0];22    }23}

Complexity

Time

O(N^2)

Space

O(N)

Trade-offs

Pros

Highly space-efficient, meeting the follow-up requirement of O(N) extra space.
Maintains the efficient O(N^2) time complexity.

Cons

The in-place update of the 1D array can be slightly less intuitive to grasp initially compared to the 2D DP table.

If modifying the input triangle is permissible, we can achieve the ultimate space optimization by using the triangle itself as our DP table. This eliminates the need for any extra space apart from a few variables for iteration, resulting in O(1) extra space complexity.

Algorithm

Iterate from the second-to-last row (i = N-2) up to the first row (i = 0).
For each row i, iterate through its elements from j = 0 to j = i.
In-place Update: Calculate the minimum path sum from the current cell (i, j) by adding its value to the minimum of the two adjacent cells in the row below (triangle[i+1][j] and triangle[i+1][j+1]).
Update the value of triangle[i][j] with this new sum.
- triangle[i].set(j, triangle[i][j] + min(triangle[i+1][j], triangle[i+1][j+1]))
Result: After the loops complete, the original top element triangle[0][0] will be overwritten with the minimum total path sum.

Walkthrough

This is the most space-efficient approach. It uses the same bottom-up logic as the previous methods but cleverly reuses the input triangle list to store the intermediate DP values. We iterate from the second-to-last row upwards. For each element triangle[i][j], we update its value to be the sum of its original value and the minimum of the two elements directly below it in the next row. By the time the process reaches the top row, the element triangle[0][0] will contain the overall minimum path sum.

1class Solution {2    public int minimumTotal(List<List<Integer>> triangle) {3        int n = triangle.size();4 5        // Iterate from the second to last row up to the top6        for (int i = n - 2; i >= 0; i--) {7            for (int j = 0; j <= i; j++) {8                // Find the minimum of the two adjacent numbers in the row below9                int minSumBelow = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1));10                11                // Update the current number with the sum of itself and the minimum from below12                int currentVal = triangle.get(i).get(j);13                triangle.get(i).set(j, currentVal + minSumBelow);14            }15        }16 17        // The top element of the triangle now holds the minimum path sum18        return triangle.get(0).get(0);19    }20}

Complexity

Time

O(N^2)

Space

O(1)

Trade-offs

Pros

Extremely space-efficient, using O(1) extra space.
Simple and concise implementation.
Retains the O(N^2) time efficiency.

Cons

This approach modifies the input data structure, which might be undesirable if the original triangle needs to be preserved for other purposes.

Solutions

Solution

1class Solution {2public3  int minimumTotal(List<List<Integer>> triangle) {4    for (int i = triangle.size() - 2; i >= 0; --i) {5      for (int j = 0; j <= i; ++j) {6        int x = triangle.get(i).get(j);7        int y = Math.min(triangle.get(i + 1).get(j),8                         triangle.get(i + 1).get(j + 1));9        triangle.get(i).set(j, x + y);10      }11    }12    return triangle.get(0).get(0);13  }14}

1class Solution {2public:3  int minimumTotal(vector<vector<int>> &triangle) {4    for (int i = triangle.size() - 2; ~i; --i) {5      for (int j = 0; j <= i; ++j) {6        triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);7      }8    }9    return triangle[0][0];10  }11};

1class Solution : def minimumTotal ( self , triangle : List [ List [ int ]]) -> int : n = len ( triangle ) for i in range ( n - 2 , - 1 , - 1 ): for j in range ( i + 1 ): triangle [ i ][ j ] = ( min ( triangle [ i + 1 ][ j ], triangle [ i + 1 ][ j + 1 ]) + triangle [ i ][ j ] ) return triangle [ 0 ][ 0 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int minimumTotal(List<List<Integer>> triangle) {4    for (int i = triangle.size() - 2; i >= 0; --i) {5      for (int j = 0; j <= i; ++j) {6        int x = triangle.get(i).get(j);7        int y = Math.min(triangle.get(i + 1).get(j),8                         triangle.get(i + 1).get(j + 1));9        triangle.get(i).set(j, x + y);10      }11    }12    return triangle.get(0).get(0);13  }14}

1class Solution {2public:3  int minimumTotal(vector<vector<int>> &triangle) {4    for (int i = triangle.size() - 2; ~i; --i) {5      for (int j = 0; j <= i; ++j) {6        triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);7      }8    }9    return triangle[0][0];10  }11};

1class Solution : def minimumTotal ( self , triangle : List [ List [ int ]]) -> int : n = len ( triangle ) for i in range ( n - 2 , - 1 , - 1 ): for j in range ( i + 1 ): triangle [ i ][ j ] = ( min ( triangle [ i + 1 ][ j ], triangle [ i + 1 ][ j + 1 ]) + triangle [ i ][ j ] ) return triangle [ 0 ][ 0 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.