Triangle

MediumDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A number triangle is given as triangle, where row i contains i + 1 integers. Start at the single value on top and move down one row at a time; from position j in a row you may step to position j or j + 1 in the row below. Return the minimum possible sum of the values along a path from the top row to the bottom row. Try to use only O(n) extra space, where n is the number of rows.

Examples

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
The path 2 -> 3 -> 5 -> 1 sums to 11.
Input: triangle = [[-10]]
Output: -10
A single row: the path is just -10.

Constraints

  • 1 <= triangle.length <= 200
  • `triangle[0].length == 1`
  • `triangle[i].length == triangle[i-1].length + 1`
  • -10^4 <= triangle[i][j] <= 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems