Triangle

Posted: 7 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem