Compute minimum path sum in a triangle
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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`.
Quick Answer: This question evaluates proficiency in dynamic programming and algorithmic problem-solving within the Coding & Algorithms domain, focusing on handling triangular data structures, index transitions, and numeric aggregation.
Return the minimum top-to-bottom path sum in a triangle.
Constraints
- Row i has length i+1
Examples
Input: ([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]],)
Expected Output: 11
Explanation: Prompt example.
Input: ([[-10]],)
Expected Output: -10
Explanation: Single negative value.
Input: ([],)
Expected Output: 0
Explanation: Empty triangle.
Input: ([[1], [2, 3]],)
Expected Output: 3
Explanation: Two rows.
Hints
- Compute minimum suffix path sums from the bottom row upward.