Quick Overview

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.

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.

Overview: 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

  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.

Loading coding console...

Show the approach

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)