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
Solution
from typing import List
def minimum_total(triangle: List[List[int]]) -> int:
# Handle empty input defensively, though constraints guarantee at least one row
if not triangle:
return 0
# dp holds the minimum path sums from the current row to the bottom
dp = triangle[-1][:] # copy last row
# Iterate from the second-last row up to the top
for r in range(len(triangle) - 2, -1, -1):
for c in range(r + 1):
dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])
return dp[0]
Explanation
Initialize a DP array as a copy of the last row. For each cell in row r (from bottom-1 to top), set dp[c] to triangle[r][c] plus the min of dp[c] and dp[c+1], which represent the best sums from the two adjacent positions below. After processing up to the top, dp[0] is the minimum path sum.
Time complexity: O(n^2). Space complexity: O(n).
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.