Minimum Sum Path in a Triangle

Given a 'triangle' as an ArrayList of ArrayLists of integers, with each list representing a level of the triangle, find the minimum sum achieved by following a top-down path and adding the integer at each level along the path. Movement is restricted to adjacent numbers from the top to the bottom.

Note:
- You can only traverse through adjacent nodes while moving up or down the triangle.
- An adjacent node is defined as a node that is reached by moving down and left or down and right from a level. For eg, in the triangle shown below, if you are at the digit 3 in the second row, its adjacent nodes are 5 and 6

Example:

Input Triangle: 
[   [1],
   [2, 3],
  [4, 5, 6],
[7, 8, 9, 10],
]

Output : 14 (1->2->4->7)
Note: [..] denotes an ArrayList

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

This problem can be made easier by carefully considering the shape of the data structure. A triangle is naturally the widest at its base, and becomes progressively narrower as you move up towards its top. This means that a bottom-up approach is the best way to go to solve this problem.

A more detailed explanation

Use a buffer array that is the length of the base of the triangle - int[] outBuffer = new int[input.get(height-1).size()];. Fill this buffer array with the last row of the triangle. Now, move up the triangle, and at each level, iterate across the level and add to the base buffer the minimum sum of the element directly above - outBuffer[i] = row.get(i) + Math.min(outBuffer[i], outBuffer[i+1]);. Finally, return the first element of the buffer - return outBuffer[0];

public static int minTriangleDepth(ArrayList<ArrayList<Integer>> input) {
    
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Minimum Sum Path in a Triangle

Quick hint to get things rolling

A more detailed explanation

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :