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 = 11
Example 2:
Input: values = [1,2] Output: 2
Constraints:
2 <= values.length <= 5 * 1041 <= values[i] <= 1000Problem Overview: You are given an array values where each index represents a sightseeing spot. The score of a pair (i, j) with i < j is defined as values[i] + values[j] + i - j. The task is to find the maximum possible score among all valid pairs.
Approach 1: Brute Force Approach (O(n2) time, O(1) space)
The direct method checks every possible pair of indices (i, j) where i < j. For each pair, compute the score using the formula and keep track of the maximum value seen so far. This requires two nested loops: the outer loop picks the first sightseeing spot, and the inner loop evaluates every possible second spot to the right. The approach is straightforward and useful for validating correctness, but it becomes slow for large inputs because it performs roughly n*(n-1)/2 comparisons.
Approach 2: Optimized Single Pass (O(n) time, O(1) space)
The key insight comes from rewriting the formula: values[i] + values[j] + i - j becomes (values[i] + i) + (values[j] - j). While scanning the array from left to right, you maintain the best value of values[i] + i seen so far. At each position j, compute the candidate score by combining this stored maximum with values[j] - j. After evaluating the pair, update the running maximum of values[i] + i. This transforms the problem into a single linear pass over the array. The idea resembles a rolling best-state update often seen in lightweight dynamic programming patterns.
Recommended for interviews: Start by explaining the brute force approach to show you understand the scoring formula and pair constraints. Then derive the optimized form by separating the expression into two independent components. Interviewers expect the O(n) single-pass solution because it demonstrates the ability to algebraically transform the formula and maintain a running optimum.
This approach iterates through each index in the array as a starting point and computes the score for every subsequent point. It keeps track of the maximum score found.
Although simple, this approach involves nested iteration, making it inefficient for large inputs due to the O(n^2) time complexity.
The solution uses a nested loop to brute-force calculate the score for each pair of sights (i < j). The outer loop fixes 'i' while the inner loop iterates over 'j', calculates the respective score, and updates the maximum score found.
Time Complexity: O(n^2) due to the nested loops.
Space Complexity: O(1) as no additional space is used.
This approach is a much more efficient O(n) solution. It maintains a running maximal value of 'values[i] + i' to maximize the score of subsequent elements. As the array is traversed, it calculates and continuously updates the maximum possible score using this running maximum and 'values[j] - j'.
This optimized C solution iterates through the array, maintaining the maximal 'values[i] + i' seen so far and computing the current potential maximum score with 'values[j] - j'. The highest score is updated dynamically.
Time Complexity: O(n) since it makes a single pass.
Space Complexity: O(1) because additional space isn't used.
We can enumerate j from left to right while maintaining the maximum value of values[i] + i for elements to the left of j, denoted as mx. For each j, the maximum score is mx + values[j] - j. The answer is the maximum of these maximum scores for all positions.
The time complexity is O(n), where n is the length of the array values. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Approach | Time Complexity: O(n^2) due to the nested loops. |
| Approach 2: Optimized Single Pass | Time Complexity: O(n) since it makes a single pass. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n^2) | O(1) | Useful for understanding the formula or validating correctness on small inputs |
| Optimized Single Pass | O(n) | O(1) | Best general solution for large arrays and the expected interview answer |
Best Sightseeing Pair - Leetcode 1014 - Python • NeetCodeIO • 10,316 views views
Watch 9 more video solutions →Practice Best Sightseeing Pair with our built-in code editor and test cases.
Practice on FleetCode