Pick Two Trees for a Zipline That Maximizes Height Times Span
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Trees stand in a straight row, one unit apart: tree `i` is at position `i` and has height `heights[i]`. You will install one zipline between two different trees. The cable is attached at the same height on both trees, so it can be mounted no higher than the shorter of the two. Rate a zipline between trees `i` and `j` (with `i < j`) by `min(heights[i], heights[j]) * (j - i)`: the mounting height times the horizontal span. Return the highest rating any zipline can get.
### Function Signature
```python
def best_zipline(heights: list[int]) -> int:
```
### Rules
- A zipline joins two distinct trees. Trees standing between them do not block the cable and do not affect the rating.
- Return only the maximum rating, which is a single integer.
### Constraints
- `2 <= len(heights) <= 10^5`
- `1 <= heights[i] <= 10^4`
- The rating is at most `10^4 * (10^5 - 1)`, which is below `10^9` and fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: heights = [3, 1, 4, 2, 5]
Output: 12
```
Trees 0 and 4 give `min(3, 5) * (4 - 0) = 12`. Trees 2 and 4 give only `min(4, 5) * 2 = 8`.
**Example 2**
```text
Input: heights = [2, 7, 1, 7, 1, 3]
Output: 14
```
Trees 1 and 3 give `min(7, 7) * 2 = 14`, which beats the widest pair, trees 0 and 5 (`2 * 5 = 10`), and trees 1 and 5 (`3 * 4 = 12`).
**Example 3**
```text
Input: heights = [6, 9]
Output: 6
```
The only zipline joins trees 0 and 1: `min(6, 9) * 1 = 6`.
Overview: A coding question that recasts the classic two-line container problem as choosing two trees in a row to string a zipline between. It asks for the largest value of the shorter tree's height times the distance between the two trees, over arrays of up to 100,000 heights, and tests efficient pair selection.
Read the full Nuro Software Engineer interview experience this question came from
Trees stand in a straight row, one unit apart: tree `i` is at position `i` and has height `heights[i]`. You will install one zipline between two different trees. The cable is attached at the same height on both trees, so it can be mounted no higher than the shorter of the two.
The rating of a zipline between trees `i` and `j` (with `i < j`) is `min(heights[i], heights[j]) * (j - i)`: the mounting height times the horizontal span. Return the highest rating any zipline can get.
### Rules
- A zipline joins two distinct trees. Trees standing between them do not block the cable and do not affect the rating.
- Return only the maximum rating, which is a single integer.
### Constraints
- `2 <= len(heights) <= 10^5`
- `1 <= heights[i] <= 10^4`
- The rating is at most `10^4 * (10^5 - 1) = 999,990,000`, which is below `10^9`. It never exceeds `2^31 - 1`, so it fits in a 32-bit signed integer (`int` in Java and C++).
### Examples
**Example 1**
```text
Input: heights = [3, 1, 4, 2, 5]
Output: 12
```
Trees 0 and 4 give `min(3, 5) * (4 - 0) = 12`. Trees 2 and 4 give only `min(4, 5) * 2 = 8`.
**Example 2**
```text
Input: heights = [2, 7, 1, 7, 1, 3]
Output: 14
```
Trees 1 and 3 give `min(7, 7) * 2 = 14`, which beats the widest pair, trees 0 and 5 (`2 * 5 = 10`), and trees 1 and 5 (`3 * 4 = 12`).
Constraints
- 2 <= len(heights) <= 10^5
- 1 <= heights[i] <= 10^4
- The rating is at most 10^4 * (10^5 - 1) = 999,990,000, which is below 10^9; it never exceeds 2^31 - 1 and fits in a 32-bit signed integer.
Examples
Input: ([3, 1, 4, 2, 5],)
Expected Output: 12
Explanation: Source example 1: trees 0 and 4 give min(3, 5) * 4 = 12, beating trees 2 and 4 (4 * 2 = 8) and the two tallest trees.
Input: ([2, 7, 1, 7, 1, 3],)
Expected Output: 14
Explanation: Source example 2: the inner pair 1 and 3 gives 7 * 2 = 14, beating the widest pair (2 * 5 = 10) and trees 1 and 5 (3 * 4 = 12).
Hints
- A rating depends only on the two chosen trees: the shorter of their two heights and the distance between their positions. Trees in between never matter.
- Checking every pair is correct but with up to 10^5 trees that is about 5 * 10^9 pairs. Think about which pairs can be ruled out without rating them.
- Compare the widest possible zipline with narrower ones: a narrower zipline can only win if it is mounted higher.