Triangle · Interview Problem

Back to problems

Leetcode

Medium

Arrays

Dynamic Programming

Amazon

Microsoft

Triangle

Find the minimum path sum from the top to the bottom of a triangle of numbers.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Triangle Minimum Path Sum

gfg

Problem Statement

Problem

You are given a triangular array of integers. Start at the top element and move to the next row one step at a time. From position i in a row, you may move to either of the two adjacent positions in the row below.

Return the minimum possible sum of values along any path from the top to the bottom.

Notes

Each move must go to an adjacent number in the next row.
The triangle has exactly one element in the first row, two in the second, and so on.
You must choose one number from each row.

Input Format

An integer triangle triangle, where triangle[r] contains r + 1 integers.
The first row contains the starting value.

Output Format

Return a single integer: the minimum path sum from top to bottom.

Constraints

1 <= triangle.length
Each row r has exactly r + 1 elements
Values may be negative, zero, or positive integers
The answer fits in a 32-bit signed integer

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

Explanation

The minimum path is 2 -> 3 -> 5 -> 1, which sums to 11.

Example 2

Input

triangle = [[-10]]

Output

-10

Explanation

There is only one path, so the answer is the single value.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress