Maximum Sum Skyline
Company: Expedia
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Maximum Sum Skyline
You are laying out a row of `n` decorative pillars along a straight walkway. The pillars are numbered `0` through `n - 1` from left to right, and pillar `i` is placed at position `i`.
You are given a 0-indexed integer array `capacities` of length `n`, where `capacities[i]` is the **maximum allowed height** of pillar `i` due to clearance limits at that position.
You must choose an integer height `heights[i]` for every pillar so that the resulting layout is a **valid skyline**. A layout is a valid skyline when both of the following hold:
1. **Height bounds:** for every index `i`, `1 <= heights[i] <= capacities[i]`.
2. **Single-peak shape:** the heights first rise (non-strictly) and then fall (non-strictly). Formally, there must exist a peak index `p` (with `0 <= p <= n - 1`) such that:
- for all `j` with `0 < j <= p`: `heights[j - 1] <= heights[j]`, and
- for all `k` with `p <= k < n - 1`: `heights[k + 1] <= heights[k]`.
In words: heights are non-decreasing up to the peak `p`, then non-increasing after it. A strictly increasing array (peak at the last index) and a strictly decreasing array (peak at index `0`) are both valid, as is any array that goes up then down through a single peak.
Return the **maximum possible sum** `heights[0] + heights[1] + ... + heights[n - 1]` over all valid skylines.
### Example 1
```
Input: capacities = [5, 3, 4, 1, 1]
Output: 13
```
Explanation: one optimal layout is `heights = [5, 3, 3, 1, 1]` with peak index `0`, giving a sum of `5 + 3 + 3 + 1 + 1 = 13`. No valid single-peak layout achieves a larger sum.
### Example 2
```
Input: capacities = [6, 5, 3, 9, 2, 7]
Output: 22
```
Explanation: one optimal layout is `heights = [3, 3, 3, 9, 2, 2]` with peak index `3`, giving a sum of `3 + 3 + 3 + 9 + 2 + 2 = 22`.
### Constraints
- `1 <= n == capacities.length <= 10^5`
- `1 <= capacities[i] <= 10^9`
A solution that picks the peak position by brute force and expands greedily from it is too slow for the largest inputs; aim for an approach that runs in roughly linear time.
Quick Answer: This question tests algorithmic problem-solving with array optimization under a mountain (single-peak) shape constraint. It evaluates practical application of greedy strategies and stack-based linear-time techniques, commonly asked to assess a candidate's ability to optimize beyond brute-force enumeration.
You are laying out a row of `n` decorative pillars along a straight walkway. The pillars are numbered `0` through `n - 1` from left to right, and pillar `i` is placed at position `i`.
You are given a 0-indexed integer array `capacities` of length `n`, where `capacities[i]` is the **maximum allowed height** of pillar `i` due to clearance limits at that position.
You must choose an integer height `heights[i]` for every pillar so that the resulting layout is a **valid skyline**. A layout is a valid skyline when both of the following hold:
1. **Height bounds:** for every index `i`, `1 <= heights[i] <= capacities[i]`.
2. **Single-peak shape:** the heights first rise (non-strictly) and then fall (non-strictly). Formally, there must exist a peak index `p` (with `0 <= p <= n - 1`) such that:
- for all `j` with `0 < j <= p`: `heights[j - 1] <= heights[j]`, and
- for all `k` with `p <= k < n - 1`: `heights[k + 1] <= heights[k]`.
In words: heights are non-decreasing up to the peak `p`, then non-increasing after it. A strictly increasing array (peak at the last index) and a strictly decreasing array (peak at index `0`) are both valid, as is any array that goes up then down through a single peak.
Return the **maximum possible sum** `heights[0] + heights[1] + ... + heights[n - 1]` over all valid skylines.
**Example 1**
```
Input: capacities = [5, 3, 4, 1, 1]
Output: 13
```
Explanation: one optimal layout is `heights = [5, 3, 3, 1, 1]` with peak index `0`, giving a sum of `5 + 3 + 3 + 1 + 1 = 13`.
**Example 2**
```
Input: capacities = [6, 5, 3, 9, 2, 7]
Output: 22
```
Explanation: one optimal layout is `heights = [3, 3, 3, 9, 2, 2]` with peak index `3`, giving a sum of `3 + 3 + 3 + 9 + 2 + 2 = 22`.
Constraints
- 1 <= n == capacities.length <= 10^5
- 1 <= capacities[i] <= 10^9
- The answer can exceed 32-bit range (up to ~10^14), so use a 64-bit integer type.
Examples
Input: ([5, 3, 4, 1, 1],)
Expected Output: 13
Explanation: Best layout heights = [5, 3, 3, 1, 1] with peak at index 0; sum = 13.
Input: ([6, 5, 3, 9, 2, 7],)
Expected Output: 22
Explanation: Best layout heights = [3, 3, 3, 9, 2, 2] with peak at index 3; sum = 22.
Input: ([1],)
Expected Output: 1
Explanation: Single pillar must have height between 1 and 1, so the only sum is 1.
Input: ([3, 2, 5, 5, 2, 3],)
Expected Output: 18
Explanation: Peaking on the central plateau, e.g. heights = [2, 2, 5, 5, 2, 2] gives sum 18; no single-peak layout does better.
Input: ([1000000000, 1000000000, 1000000000],)
Expected Output: 3000000000
Explanation: All caps equal, so every pillar can reach 1e9; sum = 3e9, demonstrating the need for 64-bit arithmetic.
Input: ([5, 4, 3, 2, 1],)
Expected Output: 15
Explanation: Already strictly decreasing (peak at index 0); use full capacities for sum 15.
Input: ([1, 2, 3, 4, 5],)
Expected Output: 15
Explanation: Already strictly increasing (peak at the last index); use full capacities for sum 15.
Input: ([2, 2, 2],)
Expected Output: 6
Explanation: Flat array is a valid skyline (any peak works); sum = 6.
Hints
- Fix the peak index p. Once the peak is fixed, the left part [0..p] must be non-decreasing ending at heights[p], and the right part [p..n-1] must be non-increasing starting at heights[p]. The two sides are independent given heights[p] = capacities[p].
- Compute prefix[i] = the max sum of a non-decreasing arrangement of heights[0..i] where heights[i] = capacities[i]. Similarly compute suffix[i] for a non-increasing arrangement of heights[i..n-1]. The answer for peak i is prefix[i] + suffix[i] - capacities[i].
- To compute prefix[i] in O(n) overall, use a monotonic stack. When you reach index i, pop all earlier indices whose capacity exceeds capacities[i] (they must be flattened down to capacities[i]). If the nearest remaining smaller-or-equal index is j, then prefix[i] = prefix[j] + (i - j) * capacities[i]; if the stack is empty, prefix[i] = (i + 1) * capacities[i]. Mirror this scanning right-to-left for suffix[i].
- Use 64-bit integers: with n up to 1e5 and capacities up to 1e9 the running sums can reach about 1e14.