Home Roadmap Courses Problems Dashboard Pricing

Home Roadmap Courses Problems Dashboard Pricing

Loading editor…

Problem 215

Triangle

Medium2D DP

triangle[i] has i+1 numbers. From an index you may step to the same index or index+1 on the next row. Return the minimum path sum from top to bottom.

Examples

Example 1

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

Output: 11

Example 2

Input: [[[-10]]]

Output: -10

Constraints

Inputs fit in standard 32-bit integers unless noted.

Target ComplexityNot required

O(n · states) Time · O(n · states) Space

Companies (6)

AmazonGoogleMetaMicrosoftAppleBloomberg

Node 22.08.0

Loading editor…

Test casesRun to compare output

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

Expected11

Output—