Best Sightseeing Pair (LeetCode 1014)
You get an integer array values. Each position is one sightseeing spot along a road, and values[i] is how good spot i is. A pair is two different spots i and j with i < j.
The score of a pair is the two values added together, minus the distance between the spots: values[i] + values[j] - (j - i). Return the highest score that any pair can have.
Worked Examples
values = [8,1,5,2,6]118 + 5 - 2 = 11. Every other pair scores less.values = [1,2]21 + 2 - 1 = 2.⚖️Formal Constraints & Bounds
2 <= values.length <= 5 * 1041 <= values[i] <= 1000
Core Insight
The score splits into a part that needs only the left spot, values[i] + i, and a part that needs only the right spot, values[j] - j. So for each right spot the best partner is the earlier spot with the largest values[i] + i, and one carried maximum replaces the search over all pairs.
Real-World Scenario & Production Applications
A tour guide picks two stops on one road. Each stop has a rating, and every stop between the two costs one point of walking. The best tour is the pair with the highest ratings and the least walking.
Step-by-Step Execution Trace Table
Trace of Example 1: values = [8, 1, 5, 2, 6]. best_left = 8 (spot 0, 8 + 0) and best = -inf.
j | values[j] | best = max(best, best_left + values[j] - j) | best_left = max(best_left, values[j] + j) |
|---|---|---|---|
| 1 | 1 | max(-inf, 8 + 1 - 1) = 8 | max(8, 1 + 1) = 8 |
| 2 | 5 | max(8, 8 + 5 - 2) = 11 | max(8, 5 + 2) = 8 |
| 3 | 2 | max(11, 8 + 2 - 3) = 11 | max(8, 2 + 3) = 8 |
| 4 | 6 | max(11, 8 + 6 - 4) = 11 | max(8, 6 + 4) = 10 |
At j = 2, the best earlier spot is spot 0, so the score is 11. At j = 4, best_left is still 8, because best_left is updated with spot 4 only after spot 4 is scored.
| 1 | best_left = values[0]; best = float('-inf') |
| 2 | for j in range(1, len(values)): |
| 3 | best = max(best, best_left + values[j] - j) |
| 4 | best_left = max(best_left, values[j] + j) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A pair of spots i < j has the score values[i] + values[j] + i - j. Trying every pair takes N * (N - 1) / 2 checks. The score can be regrouped as (values[i] + i) + (values[j] - j). The first part needs only i. The second part needs only j.
➗ What Is Carried From The Left
For one right end j, the second part is fixed. The best score for j uses the earlier spot with the largest values[i] + i. One variable, best_left, keeps that largest value. It is the whole state of the DP.
🔑 The Key Idea in the Code
The loop scores j first and updates best_left with j second. If the order is reversed, best_left already contains spot j, and the spot is paired with itself.
Updating
best_leftwith spotjbefore scoringj:best_leftthen contains spotj, and the pair uses the same spot twice.[8, 1, 5, 2, 6]returns 12 instead of 11.Carrying
values[i]instead ofvalues[i] + i: the distance is part of the left term.[1, 1, 1, 1, 9]returns 6 instead of 9.Leaving out
- jfrom the score: the distance is never subtracted.[8, 1, 5, 2, 6]returns 14 instead of 11.Starting the loop at
j = 0: spot 0 is scored against itself.[8, 1, 5, 2, 6]returns 16 instead of 11.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Maximum score of a pair of spots" with the score values[i] + values[j] + i - j: the pair must be in order (i < j), and the score adds a term for i and a term for j. When a pair score separates into one term for each end, the best left end can be carried while the loop moves right.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before spot j is scored, best_left is the largest values[i] + i over all spots i < j, and best is the largest score of any pair that ends before j. The score of j is best_left + values[j] - j.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with the best left half carry. The score values i plus values j plus i minus j can be regrouped as values i plus i, plus values j minus j. The first part needs only the left spot and the second part needs only the right spot. So for each right spot j, the best partner is the earlier spot with the largest values i plus i. I keep that in one variable, best left, which starts as the first spot. For each j from one on, I first score the pair, best left plus values j minus j, and keep the maximum. Only after that, I update best left with values j plus j. If I updated first, j would pair with itself. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for j in range(1, len(values)) visits each spot after the first once. Each visit does one max to score j and one max to update best_left, which is constant work. That is N - 1 steps, so time is O(N).
O(1)
The code keeps two variables, best_left and best, whatever the length of values is. There is no table and no recursion, so space is O(1).
Derivation Progression
for j in range(1, len(values)) visits each spot after the first once.
2 = O(1)
One max for best and one max for best_left.
2(N - 1) = O(N)
Spots times a constant amount of work.
Variable Definitions
Length of values
Largest values[i] + i over the spots before j
Largest pair score found so far
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables best_left and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every spot.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum score of a pair of spots", "i < j". A pair score that adds a term for each end and subtracts the distance can be regrouped into a left part and a right part, so the best left end is carried while the loop moves right.
and . Scoring every pair is about pairs in the worst case, which is too slow. One pass is . The carried value values[i] + i is at most about , so 32-bit integers are enough.
Updating best_left before scoring j pairs j with itself, and [8, 1, 5, 2, 6] returns 12 instead of 11. Starting the loop at j = 0 does the same with spot 0. best starts at minus infinity so that the first real score replaces it.
Best Sightseeing Pair (LeetCode 1014)
You get an integer array values. Each position is one sightseeing spot along a road, and values[i] is how good spot i is. A pair is two different spots i and j with i < j.
The score of a pair is the two values added together, minus the distance between the spots: values[i] + values[j] - (j - i). Return the highest score that any pair can have.
Worked Examples
values = [8,1,5,2,6]118 + 5 - 2 = 11. Every other pair scores less.values = [1,2]21 + 2 - 1 = 2.⚖️Formal Constraints & Bounds
2 <= values.length <= 5 * 1041 <= values[i] <= 1000
Core Insight
The score splits into a part that needs only the left spot, values[i] + i, and a part that needs only the right spot, values[j] - j. So for each right spot the best partner is the earlier spot with the largest values[i] + i, and one carried maximum replaces the search over all pairs.
Real-World Scenario & Production Applications
A tour guide picks two stops on one road. Each stop has a rating, and every stop between the two costs one point of walking. The best tour is the pair with the highest ratings and the least walking.
Step-by-Step Execution Trace Table
Trace of Example 1: values = [8, 1, 5, 2, 6]. best_left = 8 (spot 0, 8 + 0) and best = -inf.
j | values[j] | best = max(best, best_left + values[j] - j) | best_left = max(best_left, values[j] + j) |
|---|---|---|---|
| 1 | 1 | max(-inf, 8 + 1 - 1) = 8 | max(8, 1 + 1) = 8 |
| 2 | 5 | max(8, 8 + 5 - 2) = 11 | max(8, 5 + 2) = 8 |
| 3 | 2 | max(11, 8 + 2 - 3) = 11 | max(8, 2 + 3) = 8 |
| 4 | 6 | max(11, 8 + 6 - 4) = 11 | max(8, 6 + 4) = 10 |
At j = 2, the best earlier spot is spot 0, so the score is 11. At j = 4, best_left is still 8, because best_left is updated with spot 4 only after spot 4 is scored.
| 1 | best_left = values[0]; best = float('-inf') |
| 2 | for j in range(1, len(values)): |
| 3 | best = max(best, best_left + values[j] - j) |
| 4 | best_left = max(best_left, values[j] + j) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A pair of spots i < j has the score values[i] + values[j] + i - j. Trying every pair takes N * (N - 1) / 2 checks. The score can be regrouped as (values[i] + i) + (values[j] - j). The first part needs only i. The second part needs only j.
➗ What Is Carried From The Left
For one right end j, the second part is fixed. The best score for j uses the earlier spot with the largest values[i] + i. One variable, best_left, keeps that largest value. It is the whole state of the DP.
🔑 The Key Idea in the Code
The loop scores j first and updates best_left with j second. If the order is reversed, best_left already contains spot j, and the spot is paired with itself.
Updating
best_leftwith spotjbefore scoringj:best_leftthen contains spotj, and the pair uses the same spot twice.[8, 1, 5, 2, 6]returns 12 instead of 11.Carrying
values[i]instead ofvalues[i] + i: the distance is part of the left term.[1, 1, 1, 1, 9]returns 6 instead of 9.Leaving out
- jfrom the score: the distance is never subtracted.[8, 1, 5, 2, 6]returns 14 instead of 11.Starting the loop at
j = 0: spot 0 is scored against itself.[8, 1, 5, 2, 6]returns 16 instead of 11.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Maximum score of a pair of spots" with the score values[i] + values[j] + i - j: the pair must be in order (i < j), and the score adds a term for i and a term for j. When a pair score separates into one term for each end, the best left end can be carried while the loop moves right.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before spot j is scored, best_left is the largest values[i] + i over all spots i < j, and best is the largest score of any pair that ends before j. The score of j is best_left + values[j] - j.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with the best left half carry. The score values i plus values j plus i minus j can be regrouped as values i plus i, plus values j minus j. The first part needs only the left spot and the second part needs only the right spot. So for each right spot j, the best partner is the earlier spot with the largest values i plus i. I keep that in one variable, best left, which starts as the first spot. For each j from one on, I first score the pair, best left plus values j minus j, and keep the maximum. Only after that, I update best left with values j plus j. If I updated first, j would pair with itself. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for j in range(1, len(values)) visits each spot after the first once. Each visit does one max to score j and one max to update best_left, which is constant work. That is N - 1 steps, so time is O(N).
O(1)
The code keeps two variables, best_left and best, whatever the length of values is. There is no table and no recursion, so space is O(1).
Derivation Progression
for j in range(1, len(values)) visits each spot after the first once.
2 = O(1)
One max for best and one max for best_left.
2(N - 1) = O(N)
Spots times a constant amount of work.
Variable Definitions
Length of values
Largest values[i] + i over the spots before j
Largest pair score found so far
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables best_left and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every spot.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum score of a pair of spots", "i < j". A pair score that adds a term for each end and subtracts the distance can be regrouped into a left part and a right part, so the best left end is carried while the loop moves right.
and . Scoring every pair is about pairs in the worst case, which is too slow. One pass is . The carried value values[i] + i is at most about , so 32-bit integers are enough.
Updating best_left before scoring j pairs j with itself, and [8, 1, 5, 2, 6] returns 12 instead of 11. Starting the loop at j = 0 does the same with spot 0. best starts at minus infinity so that the first real score replaces it.