/120. Minimum Path Sum in Triangle Array
Previous|Next

120. Minimum Path Sum in Triangle Array

Medium
Arrays59.9% acceptance

Given a list of lists of integers named matrix, where each sublist represents a row of a triangle-shaped array, compute the minimum sum of a path from the top row to the bottom row. At each step, you may move to either the same index or the next index in the row directly below. Return the minimum possible path sum.

Example 1

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

Output: 14

Explanation: Path: 1 -> 2 -> 4 -> 7 = 14

Example 2

Input: [[5],[6,7],[8,9,10],[11,12,13,14]]

Output: 30

Explanation: Path: 5 -> 6 -> 8 -> 11 = 30

Constraints

  • 1 <= len(matrix) <= 200
  • matrix[0] has length 1
  • For all i > 0, len(matrix[i]) == len(matrix[i-1]) + 1
  • -104 <= matrix[i][j] <= 104
Python (current runtime)

Case 1

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

Expected: 10

Case 2

Input: [[7],[3,8],[8,1,0],[2,7,4,4]]

Expected: 11

Case 3

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

Expected: 12

Case 4

Input: [[10]]

Expected: 10