Pick Two Trees for a Zipline That Maximizes Height Times Span

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

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

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

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

Input:  heights = [6, 9]
Output: 6

The only zipline joins trees 0 and 1: min(6, 9) * 1 = 6.

Highest-Rated Zipline Between Two Trees

Hints

1. 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.
2. 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.
3. Compare the widest possible zipline with narrower ones: a narrower zipline can only win if it is mounted higher.

Approach

Two pointers from the ends. Start with i = 0, j = n - 1 and best = 0. At each step rate the pair (i, j), keep the larger of that rating and best, then discard the endpoint with the smaller height (discard j when the two heights are equal). Discarding is safe: if heights[i] <= heights[j], every other pair (i, k) with i < k < j has a shorter span k - i < j - i and a mounting height min(heights[i], heights[k]) <= heights[i] = min(heights[i], heights[j]), so it rates no higher than the pair (i, j) just evaluated; tree i cannot be part of any better pair among the trees still in [i, j]. The symmetric argument covers discarding j when heights[j] <= heights[i], which also makes the tie choice irrelevant. Invariant: every pair that could still beat best has both endpoints inside [i, j]. Each step shrinks the window by one, so after exactly n - 1 evaluations i == j and best equals the maximum over all pairs. Edge cases: with n = 2 the single pair is evaluated once; every height is at least 1, so the answer is at least 1; trees between the endpoints never affect a rating, so no blocking check is needed; the largest possible rating, 10^4 * (10^5 - 1) = 999,990,000, fits in a 32-bit signed integer, so int is exact in Java and C++ and a JavaScript number is exact.

• Time complexity: O(n)
• Space complexity: O(1)