Last Updated: 7 Mar, 2021
Triangle
Moderate
Asked in companies
You are given a triangular array/list 'TRIANGLE'. Your task is to return the minimum path sum to reach from the top to the bottom row.
The triangle array will have N rows and the i-th row, where 0 <= i < N will have i + 1 elements.
You can move only to the adjacent number of row below each step. For example, if you are at index j in row i, then you can move to i or i + 1 index in row j + 1 in each step.
For Example :
If the array given is 'TRIANGLE' = [[1], [2,3], [3,6,7], [8,9,6,1]] the triangle array will look like:
1
2,3
3,6,7
8,9,6,10
For the given triangle array the minimum sum path would be 1->2->3->8. Hence the answer would be 14.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains an integer ‘N’ representing the length of the array/list triangle.
Then N lines follow. Each of the ith row contains i + 1 space-separated integers denoting the elements of the array/list 'TRIANGLE'.
Output Format :
For each test case, print an integer X representing the minimum path sum.
Output for each test case will be printed in a separate line.
Note :
You don’t need to take input or print anything, it already has been taken care of. Just implement the function.
Constraints :
1 <= T <= 5
1 <= N <= 10^3
-10^6 <= TRIANGLE[i][pos] <= 10^6 ,
Where 'TRIANGLE[i][pos]' is the element at row = 'i' & position = 'pos' in triangle array.
Time limit: 1 sec
Approaches
We can check all the paths from top to bottom using recursion.
The algorithm will be:
- If the array is empty or the size of the array is zero, return zero.
- Then we can call a recursive function to check all the path sums.
- Start from row ‘i’ = 0 and 'POS' = ‘i’ and call the recursive function for minimum of ‘i’ + 1 , 'POS' and ‘i’ + 1, 'POS'+1;
- Return ‘ARR[i][POS]’ + min( solve(i + 1 , 'POS'), solve( i + 1, 'POS' + 1));
- If ‘i’ > N - 1, the recursion will terminate.
We can optimize the brute force recursive approach using memoization. We can start from the top row, and store the result for every step in an array. Whenever we get the repeating problem, we can use the stored result instead of calculating again.
Below are the steps:
- Initialize a 2D array 'DP' of size 'N'*'N' where 'N' is the number of rows in the triangle array.
- Fill all the elements of the 'DP' as INT_MAX.
- Start from the top row if the value of 'DP[i][POS]’ != INT_MAX, then return the value at the 'DP[i][POS]’.
- Else calculate the value using the recursive approach and store that in 'DP[i][POS]’, and return 'DP[i][POS]’.
We can make two dimensional ‘DP’ table and we know the base cases as now we are filling our 'DP' table in a bottom-up manner.
Below are the steps :
- Initialize a two-dimensional array of size 'N'*'N' .
- Start with the bottom-most row of triangle and fill your 'DP' table , for the last row ‘DP[ N-1 ][ POS ]’ = ‘ARR[ N-1 ][ POS ]’ ; for all ‘POS’ from 0 to 'N'-1;
- Start filling your 'DP' table this way , 'DP[ i ][ POS ]’ = min('DP[ i+1 ][ POS ]’ , 'DP[ i+1 ] [ POS+1 ]’) + ’ARR[ i ][ POS ]’, for all ‘POS’ from 0 to ‘ROWSIZE’ - 1
- Fill it for all rows till 0th row using the recurrence
Note: 'DP[0][0]’ gives the result in bottom-up fashion.
We can make a 1D ‘DP’ array and update it using the bottom-up approach.
Below are the steps :
- Initialize a 1D ‘DP’ array of size ‘N’ where ‘N’ is the number of rows in the triangle array.
- Run a loop for each row (say iterator = ‘i’) :
- For row ‘i’, update the ‘DP’ array as :
- Now each ‘POS’ from 0 to ‘i’ :
- ‘DP[POS]’ = min(‘DP[POS]’ , ’DP[POS+1]’) + ‘ARR[i][POS]’.
- Now each ‘POS’ from 0 to ‘i’ :
Similar problems