Find Minimum Path Sum in Integer Triangle

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.

Minimum Path Sum in Triangle

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

Examples

Example 1

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11

Explanation: A minimum path is 2 -> 3 -> 5 -> 1, sum = 11.

Example 2

Input: triangle = [[-1],[2,3],[1,-1,-3]]
Output: -1

Explanation: A minimum path is -1 -> 3 -> -3, sum = -1.

Hints

1. Work bottom-up: the minimum path to a cell is its value plus the min of the two reachable cells below it.
2. Use a 1D DP array initialized with the last row to achieve O(n) extra space.
3. Iterate from the second-last row up to the top, updating DP in place.

Approach

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)