Maximum Triangle Path Sum, Overall and Through a Required Cell
Company: Airwallex
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
A number triangle has `n` rows. Row `i` (0-indexed) holds `i + 1` integers, so `triangle[i][j]` exists for `0 <= j <= i`.
A path starts at the single value in row `0` and moves down one row at a time until it reaches row `n - 1`. From position `j` in row `i`, the next step goes to position `j` or position `j + 1` in row `i + 1`. The sum of a path is the total of all `n` values it visits.
Compute two values:
1. `best_overall`: the maximum sum over all top-to-bottom paths.
2. `best_through`: the maximum sum over the top-to-bottom paths that pass through the fixed cell `(r, c)`, that is, the paths that visit `triangle[r][c]`.
Return `[best_overall, best_through]`.
### Function Signature
```python
def triangle_max_paths(triangle: list[list[int]], r: int, c: int) -> list[int]:
```
### Rules
- Every path visits exactly one value in each row, starting at the apex and ending in the bottom row.
- Every cell of the triangle lies on at least one top-to-bottom path, so `best_through` always exists.
- Values may be negative; a path cannot stop early or skip a row to avoid them.
### Constraints
- `1 <= n <= 200`
- `len(triangle[i]) == i + 1` for every row `i`
- `-10^4 <= triangle[i][j] <= 10^4`
- `0 <= r <= n - 1` and `0 <= c <= r`
- Every path sum lies between `-2 * 10^6` and `2 * 10^6`, well inside the 32-bit range.
### Examples
**Example 1**
```text
Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]], r = 1, c = 0
Output: [21, 18]
```
The best path overall is 2 → 4 → 7 → 8 = 21. A path through the 3 in row 1 reaches at most 2 → 3 → 5 → 8 = 18.
**Example 2**
```text
Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]], r = 3, c = 0
Output: [21, 15]
```
Only one path reaches the bottom-left corner: 2 → 3 → 6 → 4 = 15.
**Example 3**
```text
Input: triangle = [[-5]], r = 0, c = 0
Output: [-5, -5]
```
Overview: Given an integer triangle where each step moves to one of the two adjacent cells in the next row, return the maximum top-to-bottom path sum and the maximum sum among paths forced through a given cell. Tests dynamic programming on a triangle and adapting it to a constrained follow-up.
Read the full Airwallex Backend Engineer interview experience this question came from
Community answers
Answer by luckyzzh1989
DP, scan two times, from up to down, from down to up.
time: O(m * n)
space: O(n)
class Solution {
/**
x
xx
xxx
xxxx
xxxxx
*/
public int[] triangle_max_paths(int[][] triangle, int r, int c) {
int[] res = new int[2];
if (triangle == null || triangle.length == 0) return new int[0];
int m = triangle.length;
int n = triangle[m - 1].length;
upToDown(triangle, r, c, n, res);
downToUp(triangle, r, c, m, res);
res[1] -= triangle[r][c];
return res;
}
private void upToDown(int[][] triangle, int r, int c, int n, int[] res) {
int[] dp = new int[n];
dp[0] = triangle[0][0];
for (int i = 1; i < triangle.length; i++) {
if (i > r) break;
dp[triangle[i].length - 1] = dp[triangle[i].length - 2] + triangle[i][triangle[i].length - 1];
for (int j = triangle[i].length - 2; j >= 1; j--) {
dp[j] = Math.max(dp[j], dp[j - 1]) + triangle[i][j];
}
dp[0] += triangle[i][0];
}
res[1] = dp[c];
}
private void downToUp(int[][] triangle, int r, int c, int m, int[] res) {
int[] dp = triangle[m - 1].clone();
if (r == m - 1) res[1] += dp[c];
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j < triangle[i].length; j++) {
dp[j] = Math.max(dp[j], dp[j + 1]) + triangle[i][j];
}
if (i == r) {
res[1] += dp[c];
}
}
res[0] = dp[0];
}
}