Minimum sum path in a triangle

You are in an Amazon on-site and the interviewer draws a triangle of numbers on the whiteboard. "Find the minimum sum path from top to bottom." This problem, also commonly known as Triangle on other platforms, tests whether you can spot overlapping subproblems and apply bottom-up dynamic programming with an efficient space optimization. It is a favorite among interviewers at Amazon and Bloomberg.

TL;DR

Use bottom-up dynamic programming. Copy the last row into a memo array, then iterate upward. For each cell, set memo[i] = triangle[level][i] + min(memo[i], memo[i+1]). After processing all levels, memo[0] holds the answer. This runs in O(n) time and O(k) space, where n is the total number of elements and k is the number of rows.

Why This Problem Matters

The triangle minimum path sum is a gateway problem for dynamic programming. It introduces the concept of bottom-up DP with space optimization, a pattern that appears in dozens of harder problems: longest common subsequence, edit distance, coin change, and more. If you can reduce a 2D DP table to a 1D array here, you can apply the same trick elsewhere.

Understanding the Problem

Given a triangle represented as a nested list of integers, find the path from top to bottom with the minimum total sum. At each step, you can only move to an adjacent cell in the row below, meaning from index i you can move to index i or i + 1 on the next row.

Triangle t: [[1],[1,0],[1,2,3],[7,2,0,1]]

         1
        1 0
       1 2 3
      7 2 0 1

minPathSum(t) -> 3

The path 1 -> 0 -> 2 -> 0 sums to 3, which is the minimum possible.

Here is the triangle visualized with all adjacency connections:

Edge Cases

1. Single element: A triangle with one row and one value. The answer is that value itself.
2. Two rows: Only two possible paths. Pick the smaller child and add the root.
3. Negative values: The algorithm handles negatives naturally since min() works correctly with them.
4. All equal values: Every path has the same sum. The algorithm returns the correct result without special handling.

Solution Approach

A naive recursive approach would explore every path from top to bottom, leading to exponential time. But notice that paths overlap: cell (2, 1) with value 2 in our example can be reached from both (1, 0) and (1, 1). This overlap is the hallmark of dynamic programming.

The key insight is to work bottom-up. Start from the last row and propagate minimum path sums upward. For each cell, the minimum path sum equals its own value plus the smaller of the two path sums directly below it.

The recurrence relation is:

memo[i] = triangle[level][i] + min(memo[i], memo[i + 1])

Since we only need the row below the current one, a single 1D array suffices. Here is how the memo array evolves for our example:

And here is the minimum path highlighted in the triangle:

The path 1 -> 0 -> 2 -> 0 gives a total of 3.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.List;

public class Solution {
  public int minPathSum(List<List<Integer>> triangle) {
    int numLevels = triangle.size();

    Integer[] memo = triangle.get(numLevels - 1).toArray(Integer[]::new);

    for (int level = numLevels - 2; level >= 0; level--) {
      for (int i = 0; i <= level; i++) {
        memo[i] = triangle.get(level).get(i) + Math.min(memo[i], memo[i + 1]);
      }
    }

    return memo[0];
  }
}

Let's walk through the code:

1. Get the triangle height: numLevels tells us how many rows the triangle has.
2. Initialize memo with the last row: The minimum path sum starting from any bottom-row cell is just the cell's own value.
3. Iterate upward: Start from the second-to-last row and move toward the top. For each cell at position i, compute the minimum path sum by adding the cell's value to the smaller of memo[i] and memo[i + 1].
4. Return memo[0]: After processing all rows, the first element holds the minimum path sum from the top of the triangle to the bottom.

The inner loop only processes level + 1 elements per row, which matches the triangle's structure. Values beyond the current row in the memo array are left untouched since they are no longer needed.

Complexity Analysis

Time: O(n) where n is the total number of elements in the triangle. Each cell is processed exactly once. For a triangle with k rows, n = k * (k + 1) / 2.

Space: O(k) where k is the number of rows. We use a single array of length k (the size of the bottom row) instead of a full 2D table. This is the space optimization that makes bottom-up DP so powerful.

Why Not Top-Down?

A top-down recursive approach with memoization also works, but it has two drawbacks:

1. Recursion overhead: Each cell triggers a function call, adding stack frames and call overhead.
2. Harder to optimize space: The memo table naturally becomes 2D (indexed by level and position), making the 1D optimization less intuitive.

Bottom-up DP avoids both issues while producing identical results.

Common Pitfalls

1. Greedy doesn't work: Picking the smallest adjacent value at each step does not guarantee the global minimum. In our example, going 1 -> 1 -> 1 -> 2 = 5 is worse than 1 -> 0 -> 2 -> 0 = 3. You must consider the full path, which is exactly what DP does.

2. Off-by-one in loop bounds: The inner loop runs from 0 to level (inclusive). Using level + 1 or numLevels would access out-of-bounds indices or process cells that do not exist.

3. Forgetting to copy the last row: If you set memo = triangle.get(numLevels - 1) without copying, you modify the original triangle. Always create a copy.

4. Wrong direction: Top-down iteration would require a 2D table since each cell depends on two cells above. Bottom-up lets us use a 1D array because we overwrite values that are no longer needed.

Interview Tips

When presenting this solution:

• Start by explaining why greedy fails. Show a concrete example where the locally optimal choice leads to a suboptimal total.
• Identify the DP properties by name: overlapping subproblems (paths converge on shared cells) and optimal substructure (minimum path through a cell depends on minimum paths through its children).
• Write the recurrence relation on the whiteboard before coding: memo[i] = triangle[level][i] + min(memo[i], memo[i + 1]).
• Mention the space optimization explicitly. Going from O(n) space to O(k) shows you understand how to reduce memory usage.
• If asked for a follow-up, mention that modifying the input in-place eliminates even the O(k) space, though this mutates the caller's data.

Key Takeaways

• Bottom-up DP processes the triangle from the last row upward, building minimum path sums in a single 1D array.
• The recurrence memo[i] = triangle[level][i] + min(memo[i], memo[i+1]) captures the optimal substructure: each cell's minimum path depends on the smaller of its two children.
• Space drops from O(n) (full 2D table) to O(k) (one row) because each level only needs the row directly below it.
• Greedy fails on this problem. Always verify that a locally optimal choice leads to a globally optimal result before using greedy. When it doesn't, reach for DP.
• This pattern of reducing a 2D DP table to 1D appears in many classic problems including longest common subsequence, edit distance, and coin change.

Practice and Related Problems

Once you are comfortable with the triangle minimum path sum, try these progressions:

• Minimum path sum in a grid (movement restricted to right and down)
• Unique paths on a board (count paths instead of minimizing sum)
• Climbing stairs (1D version of the same bottom-up pattern)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, mastering bottom-up DP fundamentals like this sets a strong foundation.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def min_path_sum(self, triangle: List[List[int]]) -> int:
        num_levels = len(triangle)

        memo = triangle[num_levels - 1].copy()

        for level in range(num_levels - 2, -1, -1):
            for i in range(0, level + 1):
                memo[i] = triangle[level][i] + min(memo[i], memo[i + 1])

        return memo[0]

JavaScript

class Solution {
  minPathSum(triangle) {
    const numLevels = triangle.length;

    const memo = [...triangle[numLevels - 1]];

    for (let level = numLevels - 2; level >= 0; level--) {
      for (let i = 0; i <= level; i++) {
        memo[i] = triangle[level][i] + Math.min(memo[i], memo[i + 1]);
      }
    }

    return memo[0];
  }
}

module.exports = Solution;

TypeScript

class Solution {
  minPathSum(triangle: number[][]): number {
    const numLevels = triangle.length;

    const memo = [...triangle[numLevels - 1]];

    for (let level = numLevels - 2; level >= 0; level--) {
      for (let i = 0; i <= level; i++) {
        memo[i] = triangle[level][i] + Math.min(memo[i], memo[i + 1]);
      }
    }

    return memo[0];
  }
}

export { Solution };

C++

#include <iostream>
#include <vector>

class Solution {
public:
  int minPathSum(std::vector<std::vector<int>>& triangle) {
    int numLevels = triangle.size();

    std::vector<int> memo = triangle.back();

    for (int level = numLevels - 2; level >= 0; level--) {
      for (int i = 0; i <= level; i++) {
        memo[i] = triangle[level][i] + std::min(memo[i], memo[i + 1]);
      }
    }

    return memo[0];
  }
};

Go

package solution

import "math"

func (s *Solution) MinPathSum(triangle [][]int) int {
	numLevels := len(triangle)

	memo := make([]int, numLevels)
	copy(memo, triangle[numLevels-1])

	for level := numLevels - 2; level >= 0; level-- {
		for i := 0; i <= level; i++ {
			memo[i] = triangle[level][i] +
				int(math.Min(float64(memo[i]), float64(memo[i+1])))
		}
	}

	return memo[0]
}

type Solution struct {
}

Scala

class Solution {
  def minPathSum(triangle: List[List[Int]]): Int = {
    val numLevels = triangle.length

    val memo = triangle(numLevels - 1).toArray

    for (level <- numLevels - 2 to 0 by -1) {
      for (i <- 0 to level) {
        memo(i) = triangle(level)(i) + Math.min(memo(i), memo(i + 1))
      }
    }

    memo(0)
  }
}

Kotlin

class Solution {
    fun minPathSum(triangle: List<List<Int>>): Int {
        if (triangle.isEmpty()) return 0

        val numLevels = triangle.size

        val memo = triangle[numLevels - 1].toIntArray()

        for (level in numLevels - 2 downTo 0) {
            for (i in 0..level) {
                memo[i] = triangle[level][i] + minOf(memo[i], memo[i + 1])
            }
        }

        return memo[0]
    }
}

Swift

class Solution {
    func minPathSum(_ triangle: [[Int]]) -> Int {
        let numLevels = triangle.count

        var memo = triangle[numLevels - 1]

        for level in stride(from: numLevels - 2, through: 0, by: -1) {
            for i in 0...level {
                memo[i] = triangle[level][i] + min(memo[i], memo[i + 1])
            }
        }

        return memo[0]
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn min_path_sum(&self, triangle: Vec<Vec<i32>>) -> i32 {
        let num_levels = triangle.len();

        let mut memo = triangle[num_levels - 1].clone();

        for level in (0..num_levels - 1).rev() {
            for i in 0..=level {
                memo[i] = triangle[level][i] + memo[i].min(memo[i + 1]);
            }
        }

        memo[0]
    }
}

C#

using System;
using System.Collections.Generic;

public class Solution {
    public int MinPathSum(List<List<int>> triangle) {
        int numLevels = triangle.Count;

        var memo = triangle[numLevels - 1].ToArray();

        for (int level = numLevels - 2; level >= 0; level--) {
            for (int i = 0; i <= level; i++) {
                memo[i] = triangle[level][i] + Math.Min(memo[i], memo[i + 1]);
            }
        }

        return memo[0];
    }
}

Dart

import 'dart:math';

class Solution {
  int minPathSum(List<List<int>> triangle) {
    int numLevels = triangle.length;

    List<int> memo = List.from(triangle[numLevels - 1]);

    for (int level = numLevels - 2; level >= 0; level--) {
      for (int i = 0; i <= level; i++) {
        memo[i] = triangle[level][i] + min(memo[i], memo[i + 1]);
      }
    }

    return memo[0];
  }
}

PHP

<?php

class Solution {
    public function minPathSum(array $triangle): int {
        $numLevels = count($triangle);

        $memo = $triangle[$numLevels - 1];

        for ($level = $numLevels - 2; $level >= 0; $level--) {
            for ($i = 0; $i <= $level; $i++) {
                $memo[$i] = $triangle[$level][$i] + min($memo[$i], $memo[$i + 1]);
            }
        }

        return $memo[0];
    }
}

Ruby

class Solution
  def min_path_sum(triangle)
    num_levels = triangle.length

    memo = triangle.last.dup

    (num_levels - 2).downto(0) do |level|
      (0..level).each do |i|
        memo[i] = triangle[level][i] + [memo[i], memo[i + 1]].min
      end
    end

    memo[0]
  end
end