Best Sightseeing Pair
Understanding the Problem
The score formula values[i] + values[j] + i - j rewards spots with high values but penalizes the distance between them. Two high-value spots on opposite ends of the array can score lower than two moderate spots next to each other.
We need to find the pair (i, j) with i < j that maximizes this score. Checking every pair gives a correct but quadratic solution. The formula can also be regrouped so that each index contributes its own independent term, which reduces the problem to a single pass with a running maximum.
Key Constraints:
2 <= values.length <= 5 * 10^4: an O(n^2) scan checks about 1.25 billion pairs at the upper bound, which is too slow. The target is O(n).1 <= values[i] <= 1000: every adjacent pair scoresvalues[i] + values[i+1] - 1 >= 1, so the maximum score is always positive and initializing the answer to 0 is safe. Values cap at 1000 and indices at 5 * 10^4, so every intermediate sum fits in a 32-bit integer.
Approach 1: Brute Force
Intuition
Try every pair (i, j) where i < j, compute values[i] + values[j] + i - j, and keep the largest result. Every valid pair gets checked, so correctness is immediate. The cost is the quadratic number of pairs.
Algorithm
- Initialize
maxScoreto 0 - For each index
ifrom 0 to n-2: - For each index
jfrom i+1 to n-1: - Compute score =
values[i] + values[j] + i - j - Update
maxScoreif this score is larger - Return
maxScore
Example Walkthrough
Code
- Time Complexity: O(n^2). Two nested loops, each iterating up to n times. We check roughly n*(n-1)/2 pairs, doing O(1) work per pair.
- Space Complexity: O(1). Only a single variable
maxScoreregardless of input size.
For each index j, the inner loop rescans every previous index i to find its best left partner, even though that best partner changes only when a new element beats the current one. Carrying the best left partner forward in a single variable removes the inner loop entirely.
Approach 2: Decomposition with Running Maximum
Intuition
The score formula mixes the two indices:
values[i] + values[j] + i - j
Regrouping the terms by index separates them:
(values[i] + i) + (values[j] - j)
The score is now the sum of two independent parts. The first part, values[i] + i, depends only on the left spot. The second part, values[j] - j, depends only on the right spot. For any fixed j, maximizing the total score means maximizing values[i] + i among all i < j.
A single left-to-right scan handles that: maintain a running maximum of values[i] + i (the best left partner seen so far). At each position j, combine that running max with values[j] - j to get the best score ending at j, then check whether j itself becomes the new best left partner. The same scan-with-best-earlier-candidate pattern solves Best Time to Buy and Sell Stock.
The greedy choice is safe because no past decision ever needs to be revisited. If index k has a higher values[k] + k than every earlier index, then k is a better left partner for every future j, regardless of what values[j] - j turns out to be. The running maximum therefore always holds the optimal left partner for the current position, and evaluating it at every j covers all valid pairs.
Algorithm
- Initialize
maxLeftScoretovalues[0] + 0(thevalues[i] + icontribution of the first spot) - Initialize
maxScoreto 0 - For each index
jfrom 1 to n-1: - Compute the score using the best left partner:
maxLeftScore + values[j] - j - Update
maxScoreif this is better - Update
maxLeftScoreifvalues[j] + jis larger (this position becomes the new best left partner for future j's) - Return
maxScore
Example Walkthrough
Code
- Time Complexity: O(n). A single pass through the array, doing O(1) work per element.
- Space Complexity: O(1). Two variables (
maxLeftScoreandmaxScore) regardless of input size.