Problem Description

You are given an array values of positive integers, where each element represents the score of a sightseeing spot. You want to choose two different spots i and j (i < j) such that the score for the pair is maximized. The score for a pair is calculated as:

score = values[i] + values[j] + i - j

• You must select two distinct spots (i and j cannot be the same).
• Order matters: i must be less than j.
• Return the maximum possible score for any such pair.

Constraints:

• 2 <= values.length <= 5 * 10^4
• 1 <= values[i] <= 1000
• There is always at least one valid sightseeing pair.

Thought Process

At first glance, the problem appears to require checking all possible pairs of spots to find the one with the highest score. This brute-force approach would involve two nested loops, examining every combination, but with up to 50,000 elements, this would be too slow.

By looking closely at the formula values[i] + values[j] + i - j, we can rearrange it to (values[i] + i) + (values[j] - j). This separation hints that for each j, we want to find the best possible values[i] + i for all i < j. This insight allows us to avoid redundant calculations and optimize our approach.

The key is to keep track of the maximum values[i] + i as we iterate through the array, and at each position j, compute the score using this running maximum and values[j] - j. This way, we only need a single pass through the array.

Solution Approach

• Step 1: Initialize two variables:
  • max_i: to keep track of the maximum values[i] + i seen so far (starting with the first element).
  • max_score: to store the highest score found (initially zero or negative infinity).
• Step 2: Iterate through the array starting from the second element (since i < j).
  • For each j, calculate the score as max_i + values[j] - j.
  • Update max_score if this score is higher than the previous maximum.
  • Update max_i if values[j] + j is greater than the current max_i.
• Step 3: After looping through the array, max_score contains the highest possible score for any sightseeing pair.

This approach only requires a single pass (O(n)) and constant extra space, making it efficient even for large arrays.

Example Walkthrough

Example Input: values = [8, 1, 5, 2, 6]

1. Initialization: max_i = values[0] + 0 = 8, max_score = 0
2. j = 1:
   • Score = max_i + values[1] - 1 = 8 + 1 - 1 = 8
   • Update max_score = 8
   • values[1] + 1 = 2; max_i remains 8
3. j = 2:
   • Score = 8 + 5 - 2 = 11
   • Update max_score = 11
   • values[2] + 2 = 7; max_i remains 8
4. j = 3:
   • Score = 8 + 2 - 3 = 7
   • max_score remains 11
   • values[3] + 3 = 5; max_i remains 8
5. j = 4:
   • Score = 8 + 6 - 4 = 10
   • max_score remains 11
   • values[4] + 4 = 10; update max_i = 10

Final Answer: 11 (pair at i=0, j=2: 8+5+0-2=11)

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(n²) — because every possible pair is checked.
  • Space Complexity: O(1) — only a few variables are needed.
• Optimized Approach (described above):
  • Time Complexity: O(n) — only one pass through the array.
  • Space Complexity: O(1) — only a constant number of variables are used.

The optimized method is much more efficient and suitable for large input sizes.

Summary

The Best Sightseeing Pair problem can be solved efficiently by recognizing how the score formula can be split into two parts, allowing us to keep track of the best "prefix" as we scan through the array. This insight transforms a naive O(n²) solution into a sleek O(n) approach, making it practical for large inputs and demonstrating the power of mathematical manipulation and careful observation in algorithm design.

Code Implementation

class Solution:
    def maxScoreSightseeingPair(self, values):
        max_i = values[0] + 0
        max_score = float('-inf')
        for j in range(1, len(values)):
            score = max_i + values[j] - j
            max_score = max(max_score, score)
            max_i = max(max_i, values[j] + j)
        return max_score
      

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int max_i = values[0] + 0;
        int max_score = INT_MIN;
        for (int j = 1; j < values.size(); ++j) {
            int score = max_i + values[j] - j;
            max_score = max(max_score, score);
            max_i = max(max_i, values[j] + j);
        }
        return max_score;
    }
};
      

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int max_i = values[0] + 0;
        int max_score = Integer.MIN_VALUE;
        for (int j = 1; j < values.length; j++) {
            int score = max_i + values[j] - j;
            max_score = Math.max(max_score, score);
            max_i = Math.max(max_i, values[j] + j);
        }
        return max_score;
    }
}
      

var maxScoreSightseeingPair = function(values) {
    let max_i = values[0] + 0;
    let max_score = -Infinity;
    for (let j = 1; j < values.length; j++) {
        let score = max_i + values[j] - j;
        max_score = Math.max(max_score, score);
        max_i = Math.max(max_i, values[j] + j);
    }
    return max_score;
};