Triangle - Practice Coding Problems

Triangle - Problem

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

The triangle is represented as a 2D array where triangle[row][col] gives you the number at that position.

Input & Output

Example 1 — Basic Triangle

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

› Output: 11

💡 Note: The minimum path is 2 + 3 + 5 + 1 = 11. Path goes from top (2) → left (3) → right (5) → right (1).

Example 2 — Single Element

$ Input: triangle = [[-10]]

› Output: -10

💡 Note: Triangle with only one element, so the minimum path sum is just that element: -10.

Example 3 — Negative Numbers

$ Input: triangle = [[-1],[2,3],[1,-1,-3]]

› Output: -1

💡 Note: Optimal path: -1 + 2 + (-3) = -2, but better path is -1 + 3 + (-3) = -1.

Constraints

1 ≤ triangle.length ≤ 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10⁴ ≤ triangle[i][j] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Triangle

2D array representing triangle with path costs

Find Paths

From each position, can move to adjacent positions below

Minimum Sum

Return the smallest sum among all possible paths

Key Takeaway

🎯 Key Insight: Use bottom-up DP to build minimum path sums, with space optimization by modifying input in-place

Asked in

A Amazon 45 M Microsoft 38 G Google 32 F Facebook 28

The key insight is that this is a classic dynamic programming problem where each position's minimum path depends only on the two positions below it. The optimal approach modifies the triangle in-place, working bottom-up to compute minimum path sums. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Space-Optimized DP	O(n²)	O(1)	Modify the triangle in-place to achieve O(1) space complexity
Top-Down Dynamic Programming	O(n²)	O(n²)	Use memoization to cache results of subproblems and avoid recalculation
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible paths recursively and return the minimum sum
Bottom-Up Dynamic Programming	O(n²)	O(n²)	Build minimum path sums from bottom to top using a 2D DP table

Space-Optimized DP — Algorithm Steps

Start from second-to-last row of triangle
For each position, update with minimum path sum
Work upward until reaching the top
Return triangle[0][0] as final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Bottom Row

Bottom row already contains minimum costs (themselves)

Update In-Place

Each cell += min(below_left, below_right)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** triangle, int* triangleSizes, int numRows) {
    // Modify triangle in-place from bottom to top
    for (int i = numRows - 2; i >= 0; i--) {
        for (int j = 0; j < triangleSizes[i]; j++) {
            int left = triangle[i+1][j];
            int right = triangle[i+1][j+1];
            triangle[i][j] += (left < right ? left : right);
        }
    }
    
    return triangle[0][0];
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    int** triangle = malloc(100 * sizeof(int*));
    int* triangleSizes = malloc(100 * sizeof(int));
    int numRows = 0;
    
    char* ptr = input;
    while (*ptr) {
        if (*ptr == '[') {
            ptr++;
            triangle[numRows] = malloc(100 * sizeof(int));
            triangleSizes[numRows] = 0;
            
            while (*ptr && *ptr != ']') {
                if ((*ptr >= '0' && *ptr <= '9') || *ptr == '-') {
                    triangle[numRows][triangleSizes[numRows]] = atoi(ptr);
                    triangleSizes[numRows]++;
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                }
                if (*ptr == ',') ptr++;
            }
            numRows++;
        }
        ptr++;
    }
    
    int result = solution(triangle, triangleSizes, numRows);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Single pass through all n²/2 positions in triangle

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra variables, modifies input in-place

✓ Linear Space

78.5K Views

High Frequency

~25 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Space-Optimized DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler