Best Sightseeing Pair
Problem
Given an array of integers values, return the maximum score of a sightseeing pair, where the score of a pair (i, j) is values[i] + values[j] + i - j and i < j.
- 2 ≤ values.length ≤ 5 * 10⁴
- 1 ≤ values[i] ≤ 1000
Example
values = [8,1,5,2,6]11The brute-force approach would check all pairs (i, j) and compute values[i] + values[j] + i - j, which is O(n^2). For example, the pair (0, 2) yields 8 + 5 + 0 - 2 = 11, which is the maximum score. The key insight is to rewrite the score as (values[i] + i) + (values[j] - j), allowing a linear scan to track the best values[i] + i seen so far and combine it with values[j] - j at each step.
Approach
Straightforward Solution
A brute-force solution checks all pairs (i, j) with i < j, computing the score each time, resulting in O(n^2) time complexity, which is too slow for large inputs.
Core Observation
The score formula values[i] + values[j] + i - j can be rearranged as (values[i] + i) + (values[j] - j). This separates the problem into two parts: a prefix term and a suffix term, enabling a greedy approach.
Path to Optimal
PreviewBy rewriting the score as (values[i] + i) + (values[j] - j), the problem reduces to finding, for each j, the maximum values[i] + i for i < j…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through the array from left to right, maintaining the maximum prefix value (values[i] + i) seen so far. For each index j, compute the candidate score as best_left + values[j] - j, update the global maximum, and then update best_left with max(best_left, values[j] + j)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through the array once, updating the maximum prefix and global maximum score in constant time per element.
Space
O(1)
Only a few variables are used to track the best prefix and the global maximum score, independent of input size.
Pattern Spotlight
Greedy Algorithms (Prefix Tracking)
When a problem's scoring function can be decomposed into a sum of a prefix-dependent term and a suffix-dependent term, maintain the best prefix value while iterating to efficiently compute the maximum combined score in a single pass.
Solution
| 1 | class Solution: |
| 2 | def maxScoreSightseeingPair(self, values: list[int]) -> int: |
| 3 | best_left = values[0] |
| 4 | best = float("-inf") |
| 5 | |
| 6 | for j in range(1, len(values)): |
| 7 | best = max(best, best_left + values[j] - j) |
| 8 | best_left = max(best_left, values[j] + j) |
| 9 | |
| 10 | return best |
Step-by-Step Solution
Track Maximum Prefix Value and Update Global Maximum Score
| 3 | best_left = values[0] |
| 4 | best = float("-inf") |
| 6 | for j in range(1, len(values)): |
| 7 | best = max(best, best_left + values[j] - j) |
| 8 | best_left = max(best_left, values[j] + j) |
| 10 | return best |
Objective
To maintain the best prefix value (values[i] + i) and update the maximum sightseeing pair score in a single pass.
Key Insight
By keeping track of the maximum values[i] + i encountered so far, the algorithm can efficiently compute the score for each j as best_left + values[j] - j. Updating best_left with max(best_left, values[j] + j) ensures the prefix value is always optimal for future iterations. This approach transforms a quadratic problem into a linear one by exploiting the problem's additive structure.
Interview Quick-Check
Core Logic
Maintain a running maximum of values[i] + i to represent the best prefix, and for each j, compute the candidate score as best_left + values[j] - j, updating the global maximum accordingly.
State & Boundaries
Start best_left with values[0] because the first element is the initial prefix candidate; iterate j from 1 to end to ensure i < j.
Common Pitfalls & Bugs
Failing to update best_left after computing the score for j can cause missing better prefix candidates, leading to incorrect results.
Complexity
This single-pass approach achieves O(n) time and O(1) space, optimal for the problem constraints.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
best = max(best, best_left + values[j] - j)Update the global maximum score by comparing current best with the candidate score best_left + values[j] - j.
This line embodies the core greedy step: combining the best prefix value with the current suffix value to find the maximum score efficiently in O(1) time per iteration.
best_left = max(best_left, values[j] + j)Update best_left to be the maximum of itself and values[j] + j for future iterations.
Updating best_left ensures that the prefix value always reflects the best possible values[i] + i for all i < j, which is critical for correctness and optimality.
Full line-by-line criticality + rationale for all 6 lines available on Pro.
Test Your Understanding
Why is it valid to maintain only the maximum values[i] + i seen so far when computing the score for each j?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Best Sightseeing Pair from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Best Sightseeing Pair drill