Katkat
Back

Compute minimum path sum in a triangle

TikTokMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize path calculations in a non-linear data structure using dynamic programming, specifically focusing on space complexity optimization.

Problem Statement

Given a triangle array where each row i has i + 1 elements, write a function that finds the minimum path sum from the top to the bottom. Each step you may move to adjacent numbers on the row below. More specifically, if you are at index j in row i, you can move to either index j or index j + 1 in row i + 1.

Function Signature

def min_path_sum(triangle: List[List[int]]) -> int:

Constraints

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

Examples

Example 1: Input:

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

Output: 11 Explanation: The minimum path sum is 2 + 3 + 5 + 1 = 11.

Example 2: Input:

[
 [-10]
]

Output: -10

Edge Cases

  • A triangle with a single row.
  • Negative numbers within the triangle.
  • A triangle where all elements are the same.

Hints

Hint 1

Consider starting from the bottom of the triangle and moving upwards to simplify the decision-making process at each step.

Hint 2

Define a state where `dp[i][j]` represents the minimum path sum from the current position to the bottom of the triangle.

Hint 3

Can you reduce the space complexity to O(N) by updating a single 1D array instead of maintaining the full 2D table?

Follow-up questions

  • How would you modify your solution if you were required to return the actual path taken rather than just the sum?
  • Can you explain the space complexity of your solution and how to achieve O(N) space where N is the number of rows?
  • What changes would be necessary if you could move to any adjacent element in the row below, including diagonal neighbors, in a grid-like structure instead of a triangle?