Compute minimum path sum in a triangle

Q: Compute minimum path sum in a triangle

This is a Coding & Algorithms interview question from TikTok for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Given a triangle of integers represented as a list of rows, find the minimum path sum from the top to the bottom.

From row r and index c , you may move to row r+1 at index c or c+1 .
Return the minimum possible sum along any valid path.

Input

triangle : a list of lists of integers, where triangle[i] has length i+1 .

Output

An integer: the minimum path sum.

Constraints (typical)

1 <= number of rows <= 200
Values can be negative or positive and fit in 32-bit signed integer.

Example

Triangle:

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

Minimum path sum is 2 + 3 + 5 + 1 = 11.

Compute minimum path sum in a triangle

Input

Output

Constraints (typical)

Example

Comments (0)