Triangle

Companies:
  • Amazon Interview Questions
  • Google Interview Questions

Problem Statement

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Sample Test Cases

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Problem solution

The triangle has a tree-like structure, which would lead people to think about traversal algorithms such as DFS. However, if you look closely, you would notice that the adjacent nodes always share a ‘branch’. In other word, there are overlapping subproblems. Also, suppose x and y are ‘children’ of k. Once minimum paths from x and y to the bottom are known, the minimum path starting from k can be decided in O(1), that is optimal substructure. Therefore, dynamic programming would be the best solution to this problem in terms of time complexity.

‘Bottom-up’ DP is very straightforward: we start from the nodes on the bottom row; the min pathsums for these nodes are the values of the nodes themselves. From there, the min pathsum at the ith node on the kth row would be the lesser of the pathsums of its two children plus the value of itself, i.e.:

minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];

Or even better, since the row minpath[k+1] would be useless after minpath[k] is computed, we can simply set minpath as a 1D array, and iteratively update itself:

For the kth level:
minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i];

Complexity Analysis

Time Complexity: O(n^2) If n is the number of rows in the triangle, then time complexity is O(n^2) since we have to touch each row twice. 

Space Complexity:O(n) we have created a memorization array which has the same size as the now of rows.

Code Implementation

#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int> > &arr) {
   int memorization[arr.size()];
   int n = arr.size() - 1;
   for (int i = 0; i < arr[n].size(); ++i) {
      memorization[i] = arr[n][i];
   }
   for (int i = arr.size() - 2; i >= 0; --i) {
      for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
         memorization[j] = arr[i][j] +
         min(memorization[j],
         memorization[j + 1]);
      }
   }
   return memorization[0];
}
int main() {
   vector<vector<int> > arr = {
   {5},
   {7, 3},
   {8, 1, 2},
   {9, 6, 4, 5}};
   cout << "Minimum sum path = " << getMinSum(arr) << endl;
   return 0;
}

 

Scroll to Top