Best Sightseeing Pair
MedPrompt
You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.
The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
Example 1:
Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11Example 2:
Input: values = [1,2]
Output: 2
Constraints:
2 <= values.length <= 5 * 1041 <= values[i] <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of sightseeing spots (i, j) where i < j. For each pair, it calculates the score and keeps track of the maximum score found so far. While simple to conceptualize, it is not efficient enough for the given constraints.
Algorithm
- Initialize a variable
maxScoreto a very small number (or 0, since scores are positive). - Use a nested loop structure. The outer loop iterates with index
ifrom0ton-2. - The inner loop iterates with index
jfromi+1ton-1. - Inside the inner loop, calculate the score for the pair
(i, j):currentScore = values[i] + values[j] + i - j. - Update
maxScoreifcurrentScoreis greater:maxScore = max(maxScore, currentScore). - After both loops complete, return
maxScore.
Walkthrough
The brute-force method directly translates the problem statement into code. We use two nested loops to generate all valid pairs of indices (i, j) such that i is always less than j.
The outer loop selects the first sightseeing spot i, and the inner loop selects the second spot j from the remaining spots to the right. For each pair, we compute the score using the formula values[i] + values[j] + i - j. A variable, maxScore, is maintained throughout the process and is updated whenever a newly calculated score is higher than the current maxScore. After iterating through all possible pairs, maxScore will hold the highest possible score.
class Solution { public int maxScoreSightseeingPair(int[] values) { int maxScore = 0; int n = values.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int currentScore = values[i] + values[j] + i - j; maxScore = Math.max(maxScore, currentScore); } } return maxScore; }}Complexity
Time
O(N^2), where N is the number of sightseeing spots. The nested loops result in a quadratic number of score calculations, making it too slow for large N.
Space
O(1), as it only uses a few variables to store the maximum score and loop indices, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small input sizes.
Cons
Highly inefficient due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for large inputs, such as the ones specified in the problem constraints.
A more efficient approach is to use a single pass through the array. By rearranging the score formula values[i] + values[j] + i - j into (values[i] + i) + (values[j] - j), we can see that for each spot j, we want to find the best possible spot i (where i < j) that maximizes the values[i] + i part. We can keep track of this maximum value as we iterate through the array.
Algorithm
- Rearrange the score formula:
score = (values[i] + i) + (values[j] - j). - Initialize
maxScore = 0. - Initialize a variable
max_i_part = values[0] + 0. This variable will track the maximum value ofvalues[i] + iseen so far. - Iterate through the array with index
jfrom1ton-1. - For each
j, calculate the potential score with the bestifound so far:currentScore = max_i_part + values[j] - j. - Update the overall maximum score:
maxScore = max(maxScore, currentScore). - Update
max_i_partfor future iterations:max_i_part = max(max_i_part, values[j] + j). - Return
maxScoreafter the loop.
Walkthrough
The key to this optimization is recognizing that the score formula can be split into two independent parts: one that depends only on i and one that depends only on j. The score for a pair (i, j) is (values[i] + i) + (values[j] - j).
As we iterate through the array with an index j, our goal is to find the maximum possible score. This score is achieved by pairing the current j's contribution, values[j] - j, with the maximum possible contribution from a previous i (where i < j), which is max(values[i] + i).
We can maintain a variable, let's call it max_i_part, that stores the maximum value of values[i] + i encountered so far. We iterate from j = 1 to the end of the array. In each step, we calculate a potential score using the current j and the max_i_part we've maintained. Then, we update max_i_part with the value from the current index j (values[j] + j) if it's larger, making it available for future calculations. This allows us to find the overall maximum score in just one pass.
class Solution { public int maxScoreSightseeingPair(int[] values) { // max_i_part represents the maximum value of (values[i] + i) seen so far. // Initialize it with the value for the first element (i=0). int max_i_part = values[0] + 0; int maxScore = 0; // Iterate from the second element (j=1) to the end. for (int j = 1; j < values.length; j++) { // For the current j, the best score is pairing it with the best i (i < j). // The score is (values[i] + i) + (values[j] - j). // We use max_i_part for the (values[i] + i) part. maxScore = Math.max(maxScore, max_i_part + values[j] - j); // After using j to calculate a score, update max_i_part. // The current element j can be the 'i' for a future pair. max_i_part = Math.max(max_i_part, values[j] + j); } return maxScore; }}Complexity
Time
O(N), where N is the number of sightseeing spots. This is because we iterate through the array only once.
Space
O(1), as it only requires a few variables to store the running maximums, independent of the input size.
Trade-offs
Pros
Highly efficient with a linear time complexity, making it suitable for large inputs.
Uses constant extra space, making it memory-efficient.
Cons
The logic is less intuitive than the brute-force approach and requires an algebraic manipulation of the score formula to see the optimization.
Solutions
Solution
class Solution {public int maxScoreSightseeingPair(int[] values) { int ans = 0, mx = values[0]; for (int j = 1; j < values.length; ++j) { ans = Math.max(ans, values[j] - j + mx); mx = Math.max(mx, values[j] + j); } return ans; }}class Solution {public: int maxScoreSightseeingPair(vector<int> &values) { int ans = 0, mx = values[0]; for (int j = 1; j < values.size(); ++j) { ans = max(ans, values[j] - j + mx); mx = max(mx, values[j] + j); } return ans; }};class Solution: def maxScoreSightseeingPair(self, values: List[int]) -> int: ans, mx = 0, values[0] for j in range(1, len(values)): ans = max(ans, values[j] - j + mx) mx = max(mx, values[j] + j) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.