Best Sightseeing Pair — Solution in Python, Java & C++
Best Sightseeing Pair solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Best Sightseeing Pair is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Uber and Nutanix interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Uber, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array values where values[i] is the value of the i-th sightseeing spot. Two spots i < j are j - i apart.
The score of a pair is values[i] + values[j] + i - j. Return the maximum score over all pairs.
Example 1
Input: values = [8,1,5,2,6]
Output: 11
Explanation: Pairing spots 0 and 2: 8 + 5 + 0 - 2 = 11.
Example 2
Input: values = [1,2]
Output: 2
Example 3
Input: values = [1,3,5]
Output: 7
Constraints
2 <= values.length <= 401 <= values[i] <= 1000
Hints for Best Sightseeing Pair
Hint 1
Split the score into a left part
values[i] + iand a right partvalues[j] - j.Hint 2
Scan left to right keeping the best left part seen so far, and pair it with the current right part.
Hint 3
That turns an O(n²) pair search into one pass.
How to solve Best Sightseeing Pair
Split the score into (values[i] + i) and (values[j] - j); sweep j keeping the best left part seen so far.
Approach
- Start
bestLeft = values[0] + 0. - For each
j ≥ 1, update the answer withbestLeft + values[j] - j, thenbestLeft = max(bestLeft, values[j] + j). - Return the answer.
Why it works
The two halves of the score depend on i and j independently, so for each j the optimal i is the one maximising values[i] + i among earlier indices.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Update
bestLeftafter using it, soi < jis preserved.
Reference solution
Python
def maxScoreSightseeingPair(values) -> int:
best = float("-inf")
best_left = values[0]
for j in range(1, len(values)):
best = max(best, best_left + values[j] - j)
best_left = max(best_left, values[j] + j)
return bestJava
public static int maxScoreSightseeingPair(int[] values) {
int best = -2000000, bestLeft = values[0];
for (int j = 1; j < values.length; j++) {
best = Math.max(best, bestLeft + values[j] - j);
bestLeft = Math.max(bestLeft, values[j] + j);
}
return best;
}C++
int maxScoreSightseeingPair(vector<int>& values) {
int best = -2000000, bestLeft = values[0];
for (int j = 1; j < (int) values.size(); j++) {
best = max(best, bestLeft + values[j] - j);
bestLeft = max(bestLeft, values[j] + j);
}
return best;
}JavaScript
var maxScoreSightseeingPair = function(values) {
let best = -Infinity, bestLeft = values[0];
for (let j = 1; j < values.length; j++) {
const candidate = bestLeft + values[j] - j;
if (candidate > best) best = candidate;
if (values[j] + j > bestLeft) bestLeft = values[j] + j;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming