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 * 10^41 <= values[i] <= 1000
The description was taken from https://leetcode.com/problems/best-sightseeing-pair/.
#O(N) Time, O(1) Space
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
best = 1
left, right = 0, 1 while right < len(values):
if values[right-1] > values[left] - (right - left):
left = right - 1
pair_sum = values[left] + values[right]
penalty = right - left
best = max(best, pair_sum - penalty)
right += 1 return bestWe can see from the problem description that each pair is going to be penalized for their distance so strictly finding the two maximum numbers isn't going to be a good approach.
What we should find instead, is the two maximum numbers with the smallest distance penalty.
To achieve this, we can utilize two pointers.
Our right pointer will trail ahead and constantly be looking at the value behind it and considering it as a pair partner. For this consideration, we will take two variables into account: the greater value between this candidate number and the current left number and the current distance penalty that is being applied to the current pair.
If we find that this candidate value can yield a better sightseeing pair because it will bring a greater value than the current left number with the current penalty that is being applied, then we will set the left pointer to this candidate index which will be directly behind the right pointer.
This is how we can maximize the pair sum and minimize the pair distance.
Let's start by setting our best pair value to one.
This will be our base case because the minimum value in the array will be one according to the constraints, and the minimum array length will be two. The pair sum of two ones that are one index apart would be 1+1-1.
best = 1
Next, we will set our initial pointers at the first and second indices respectively.
left, right = 0, 1
While the right pointer hasn't gone past the end of the input array, we will continue considering pairs.
while right < len(values):
To minimize the distance penalty, we will be considering the value directly behind the right pointer as a pair partner.
If that value is greater than the current left value and its value would also overcome the current penalty that is being applied to the current pair, then we will pair it with the right pointer.
if values[right-1] > values[left] - (right - left):
left = right - 1
Once we have considered the right pointer's previous value as a candidate pair partner, we will calculate the pair sum and the pair penalty then see if we have the best sightseeing pair.
pair_sum = values[left] + values[right]
penalty = right - left
best = max(best, pair_sum - penalty)
Then, we will expand.
right += 1
After we have considered each pair, we will return the best one.
return best