Triangle

Triangle

What is this problem about?

The "Triangle coding problem" is a classic dynamic programming task. You are given a triangle array where each row has one more element than the previous one. Your goal is to find the minimum path sum from the top to the bottom. Each step you move to adjacent numbers on the row below. For example, if you are at index i in the current row, you can move to either index i or index i+1 in the next row.

Why is this asked in interviews?

This "Triangle interview question" is a staple at companies like Amazon and Microsoft because it clearly demonstrates a candidate's understanding of dynamic programming (DP). It tests your ability to break a large problem into smaller subproblems and decide between a top-down (memoization) or bottom-up (iterative) approach. It's also an excellent problem for demonstrating space optimization—reducing a 2D DP table to a 1D array.

Algorithmic pattern used

The "Array, Dynamic Programming interview pattern" is the core here. The most elegant solution is Bottom-Up DP. We start from the second-to-last row and move upwards. For each element, we add the minimum of its two children from the row below. By the time we reach the top of the triangle, the value there will be the minimum path sum. This can be done in-place, requiring $O(1)$ extra space, or in $O(N)$ extra space if we don't want to modify the input.

Example explanation

Triangle:

   2
  3 4
 6 5 7
4 1 8 3

1. Last row: [4, 1, 8, 3]
2. Second-to-last row (update with min of children):
   • 6 + min(4, 1) = 7
   • 5 + min(1, 8) = 6
   • 7 + min(8, 3) = 10 New row: [7, 6, 10]
3. Next row up:
   • 3 + min(7, 6) = 9
   • 4 + min(6, 10) = 10 New row: [9, 10]
4. Top: 2 + min(9, 10) = 11. Minimum Path Sum = 11.

Common mistakes candidates make

One frequent mistake in the "Triangle coding problem" is trying to use a "greedy" approach—always picking the smaller of the two children at each step. Greedy fails here because a small number might be hidden behind a large one. Another mistake is using a 2D array for DP when a 1D array (or even the input triangle itself) would suffice, which uses more memory than necessary.

Interview preparation tip

For the "Array, Dynamic Programming interview pattern," always look at the "Bottom-Up" approach first. It often simplifies the boundary conditions and makes space optimization much more obvious. Triangle is the perfect problem to practice the "in-place update" technique which is highly valued in performance-critical coding tasks.