Triangle

Medium15–20 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonGoogleMicrosoft

Given a triangular arrangement of numbers, and starting at the single value on top, find the minimum possible sum of any path down to the bottom row — where each step from a value moves to one of the two values directly below it in the next row (either straight down or one position to the right). This platform's judge accepts the triangle as a square n×n grid: row i's first i+1 entries are the real triangle values, and any remaining entries in that row are unused padding. Every position's cheapest finish depends only on the two positions reachable from it one row down, so working from the bottom row upward — where a value's cheapest finish is just itself — lets each row above be resolved using results the sweep already computed. By the time the sweep reaches the single apex value, it holds the minimum total for the entire triangle.

Test Case 1:

Input:triangle rows = [1], [4,2], [3,6,5], [9,7,8,2]

Output:10

Explanation:The path 1→4→3→2 (always stepping to the same column or one column right in the row below) totals 10, the cheapest route top to bottom.

Test Case 2:

Input:triangle rows = [5], [2,3]

Output:7

Explanation:The path 5→2 totals 7, beating 5→3 which totals 8.

Test Case 3:

Input:triangle rows = [-7]

Output:-7

Explanation:A single-row triangle has only one possible path: that lone value.

Constraints

◆1 ≤ number of rows in the triangle ≤ 20
◆-1000 ≤ each triangle value ≤ 1000
◆The triangle is passed as a square n×n grid: row i holds i+1 real values followed by unused padding (use 0) out to column n-1

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Standing on any position in the triangle, the cheapest total from there down to the bottom edge is that position's own value plus whichever of the two positions directly below it — same column, or one column over — leads to a cheaper finish. Once a position sits on the bottom row, there's nothing left below it, so its cheapest total is simply its own value. Recursing downward from the apex and always taking the cheaper of the two possible next steps finds the minimum path sum, though the same lower position ends up recomputed repeatedly whenever different upper paths funnel into it.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[][] triangle;
    private int n;

    public int minimumTotal(int[][] triangle) {
        this.triangle = triangle;
        this.n = triangle.length;
        return solve(0, 0);
    }

    private int solve(int i, int j) {
        if (i == n - 1) return triangle[i][j];
        int down = solve(i + 1, j);
        int diag = solve(i + 1, j + 1);
        return triangle[i][j] + Math.min(down, diag);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Work from the bottom row upward. Start by copying the bottom row's own values as the "cheapest finish from here" for each of its positions — there's nothing below them to consider. Then, one row up at a time, replace each position's stored value with its own value plus the cheaper of the two stored values directly below it (same column, or one column over) from the row that was just processed. By the time this sweep reaches the very top row, only one position remains, and it holds the minimum path sum for the whole triangle.

TimeO(n²)