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.

1. Data Structures:
   We use a single-dimensional array dp of size n + 1, where n 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.

2. Algorithm:

   • We start iterating from the second-to-last row of the triangle because the last row's values are the base case for our dp array.
   • For each row i, we iterate through its elements, where j 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] and dp[j + 1] since they are the potential ways to reach dp[j]) plus the current element's value triangle[i][j]. This update rule reflects the rule of the problem that you can only move to i or i + 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.

3. 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)), where i represents the current row index.

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.

Example 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:

1. Initialize a dp array with zeros. In this case, since we have 4 rows, the size of dp will be 4 + 1 = 5. Thus, dp = [0, 0, 0, 0, 0].

2. 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 to dp 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 index 0, the minimum path is 6 + min(dp[0], dp[1]) => 6 + min(4, 1) = 7.
  • For 5 at index 1, the minimum path is 5 + min(dp[1], dp[2]) => 5 + min(1, 8) = 6.
  • For 7 at index 2, the minimum path is 7 + min(dp[2], dp[3]) => 7 + min(8, 3) = 10.
  • Now dp is updated to [7, 6, 10, 0, 0].

• Move to the next row [3, 4]:

  • For 3 at index 0, the minimum path is 3 + min(dp[0], dp[1]) => 3 + min(7, 6) = 9.
  • For 4 at index 1, the minimum path is 4 + min(dp[1], dp[2]) => 4 + min(6, 10) = 10.
  • Update dp to [9, 10, 0, 0, 0].

• Finally, we move to the top row [2]:

  • For 2 at index 0, the minimum path is 2 + min(dp[0], dp[1]) => 2 + min(9, 10) = 11.
  • Update dp to [11, 0, 0, 0, 0].

3. By the end of the iteration, dp[0] contains the minimum path sum which is 11. 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

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.