Find Minimum Path Sum in Integer Triangle
Company: Upstart
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
Tech interview round 1 – dynamic programming challenge
##### Question
Given a triangle of integers, find the minimum path sum from top to bottom. At each step you may move to adjacent numbers on the row below.
##### Hints
Bottom-up DP or memoised recursion, O(n²) time, O(n) space.
Quick Answer: This question evaluates understanding of dynamic programming and the ability to compute optimal path sums on triangular data structures, assessing algorithmic reasoning and complexity awareness.
Given a triangle of integers (a list of rows where row i has i+1 elements), return the minimum path sum from top to bottom. At each step, you may move to one of the two adjacent numbers directly below the current position (from index j in row r to index j or j+1 in row r+1).
Constraints
- 1 <= len(triangle) <= 200
- len(triangle[i]) == i + 1 for all valid i
- -10^4 <= triangle[i][j] <= 10^4
- Answer fits in a 32-bit signed integer
Hints
- Work bottom-up: the minimum path to a cell is its value plus the min of the two reachable cells below it.
- Use a 1D DP array initialized with the last row to achieve O(n) extra space.
- Iterate from the second-last row up to the top, updating DP in place.