1014. Best Sightseeing Pair

Problem Description

In this problem, you are given an array called values, where each element values[i] signifies the value of the i-th sightseeing spot. Sightseeing spots have a score that can be calculated based on their values and their distances from each other. Specifically, if you pick two spots at indices i and j such that i < j, the score is determined by the formula values[i] + values[j] + i - j. This score accounts for both the value of each spot and the cost of distance between them, since a higher distance decreases the overall score.

The challenge is to find the maximum possible score that can be obtained from any pair of sightseeing spots (i, j).

Intuition

The obvious solution might seem to try all possible pairs and compute the score for each, but this approach is not efficient for large arrays. Instead, we can optimize by recognizing that for any spot j, we want the highest possible value of values[i] + i from all previous spots i (since i is less than j, this keeps the distance cost minimal). That is because the score values[i] + values[j] + i - j can be rewritten as (values[i] + i) + (values[j] - j).

The solution proceeds by keeping track of the maximum value of values[i] + i encountered so far as it loops from left to right across the elements of the array. For each spot j, it calculates the potential score by adding values[j] - j to this maximum. This potential score is compared to the maximum score found so far, and if it's higher, it becomes the new maximum score.

By keeping track of these two quantities — the maximum score so far, and the maximum value of values[i] + i — the solution efficiently arrives at the maximum score possible for any pair of sightseeing spots.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution approach implements a single pass algorithm with a time complexity of O(n), where n is the length of the values array. It utilizes a simple pattern that leverages the relationship between indices and their corresponding values, as described in the intuition part.

Here's the step-by-step description of the algorithm:

Initialize two variables: ans to store the maximum score found so far and mx to store the maximum value of values[i] + i seen as the array is traversed. mx is initially set to values[0] since it's the first value plus its index.
Iterate over the array starting from index 1, since the first element is already considered as part of the initial maximum value (mx).
For each sightseeing spot j (from index 1 to the end):

a. Calculate the current potential score as values[j] - j + mx. This utilizes the previously mentioned formula of the best pair score (values[i] + i) + (values[j] - j). Here, mx represents the best values[i] + i found so far, for some i < j.

b. Update ans to the greater value between itself and the current potential score. This ensures that at the end of the iteration, ans holds the maximum score of all pairs.

c. Update mx to the greater value between itself and values[j] + j. This is crucial because, as we move rightward through the array, we might find a new sightseeing spot j with a higher value of values[j] + j that could contribute to a higher pair score in the following steps.
After the loop, ans holds the maximum score for a pair that could be achieved and is returned as the result.

This single-pass algorithm is elegant and efficient as it avoids the need for a nested loop, which would result in a less efficient O(n^2) complexity. Instead, by updating mx and ans on-the-fly, it computes the maximum score in linear time, thus making it suitable for large datasets.

The python code implementing this algorithm is straightforward:

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ans, mx = 0, values[0]  # Initialize `ans` and `mx`
        for j in range(1, len(values)):  # Iterate through the array, starting from index 1
            ans = max(ans, values[j] - j + mx)  # Update the maximum score `ans`
            mx = max(mx, values[j] + j)  # Update the running maximum of `values[i] + i`
        return ans  # After iterating through the array, return the maximum score `ans`

This solution does not use any complex data structures; it only requires two variables to keep track of the scores, making it space-efficient with O(1) additional space complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following values array:

values = [8, 1, 5, 2, 6]

We want to find the maximum score sightseeing pair using the formula values[i] + values[j] + i - j. Following the steps from the solution approach:

We initialize ans to 0 and mx to values[0], so initially ans = 0 and mx = 8.
We iterate from the second element (since we already have mx starting with the first element). Now we start with j = 1, and values[1] = 1.
We perform the following actions for each j:

a. For j = 1 (value is 1), we calculate the potential score: 1 - 1 + mx = 1 - 1 + 8 = 8. Now we compare ans with this score and update ans: ans = max(0, 8) = 8.

b. Next, we update mx: mx = max(mx, values[j] + j) = max(8, 1 + 1) = 8. It remains the same since the new values[j] + j is not greater than mx.

c. Moving to j = 2 (value is 5): The potential score is 5 - 2 + mx = 5 - 2 + 8 = 11, update ans: ans = max(8, 11) = 11, and update mx : mx = max(8, 5 + 2) = 8. Again, mx does not change.

d. For j = 3 (value is 2): The potential score is 2 - 3 + mx = 2 - 3 + 8 = 7, update ans: ans = max(11, 7) = 11, and update mx: mx = max(8, 2 + 3) = 8.

e. Lastly, for j = 4 (value is 6): The potential score is 6 - 4 + mx = 6 - 4 + 8 = 10, update ans: ans = max(11, 10) = 11, and update mx: mx = max(8, 6 + 4) = 10.
At the end of the loop, ans holds the value 11, which is the maximum score that could be achieved with any pair of sightseeing spots, specifically the pair (0, 2), corresponding to the spots with values 8 and 5, respectively.

So, the result for our example values = [8, 1, 5, 2, 6] is 11, which is the maximum score sightseeing pair (values[0] + values[2] + 0 - 2). The solution was able to find this in a single linear pass as opposed to checking every possible pair, saving time and computational resources.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxScoreSightseeingPair(self, values: List[int]) -> int:
5        max_score = 0  # Initialize the maximum score to zero
6        max_value_plus_index = values[0]  # Initialize to the first value plus its index (0)
7
8        # Iterate over the array, starting from the second element (index 1)
9        for i in range(1, len(values)):
10            # Update the max score using the current value and the best previous value plus index found
11            max_score = max(max_score, values[i] - i + max_value_plus_index)
12            # Update the max_value_plus_index with the maximum of the current and the previous
13            # while accounting for the increasing index
14            max_value_plus_index = max(max_value_plus_index, values[i] + i)
15
16        # Return the maximum score found for any sightseeing pair
17        return max_score
18

1class Solution {
2    public int maxScoreSightseeingPair(int[] values) {
3        // Initialize the answer to 0. This will hold the maximum score.
4        int maxScore = 0;
5      
6        // Initialize the maximum value seen so far, which is the value at the 0th index 
7        // plus its index (because for the first element, index is 0, so it's just the value).
8        int maxValueWithIndex = values[0];
9
10        // Iterate over the array starting from the 1st index since we've already considered the 0th index.
11        for (int j = 1; j < values.length; ++j) {
12            // Update maxScore with the maximum of the current maxScore and 
13            // the score of the current sightseeing spot combined with the previous maximum.
14            // This score is computed as the value of the current element plus its 'value' score (values[j])
15            // subtracted by its distance from the start (j) plus the maxValueWithIndex.
16            maxScore = Math.max(maxScore, values[j] - j + maxValueWithIndex);
17          
18            // Update the maxValueWithIndex to be the maximum of the current maxValueWithIndex and
19            // the 'value' score of current element added to its index (values[j] + j).
20            // This accounts for the fact that as we move right, our index increases,
21            // which decreases our score, so we need to keep track of the element
22            // which will contribute the most to the score including the index.
23            maxValueWithIndex = Math.max(maxValueWithIndex, values[j] + j);
24        }
25
26        // Return the maximum score found.
27        return maxScore;
28    }
29}
30

1#include <vector>
2#include <algorithm> // For max function
3using namespace std;
4
5class Solution {
6public:
7    int maxScoreSightseeingPair(vector<int>& values) {
8        int maxScore = 0; // This will store the maximum score seen so far
9        int maxIPlusValue = values[0]; // This keeps track of the maximum (values[i] + i)
10
11        // Start from the second element because we need at least two elements for a pair
12        for (int j = 1; j < values.size(); ++j) {
13            // Update the max score considering the current element as the second member of the pair
14            // values[j] - j is the value of the second member of the pair
15            maxScore = max(maxScore, values[j] - j + maxIPlusValue);
16          
17            // Update the maxIPlusValue for the next iterations (values[i] + i)
18            // since we need to consider this element as the potential first member of the pair
19            maxIPlusValue = max(maxIPlusValue, values[j] + j);
20        }
21      
22        // Return the maximum score found amongst all sightseeing pairs
23        return maxScore;
24    }
25};
26

1/**
2 * Calculates the maximum score of a sightseeing pair among all possible pairs.
3 * The score of a pair (i, j) is defined as values[i] + values[j] + i - j.
4 *
5 * @param values - An array representing the values of each sightseeing spot.
6 * @returns The maximum score of a sightseeing pair.
7 */
8function maxScoreSightseeingPair(values: number[]): number {
9    // Initialize the answer to zero
10    let maxScore = 0;
11  
12    // Initialize `maxValueWithIndex` to the value of the first spot, 
13    // since it will be used to keep track of the best potential score for all previous spots
14    let maxValueWithIndex = values[0];
15
16    // Iterate over all the possible sightseeing spots, starting from the second one
17    for (let currentIndex = 1; currentIndex < values.length; ++currentIndex) {
18        // Calculate the current pair score considering the current index and the max value identified so far
19        maxScore = Math.max(maxScore, values[currentIndex] - currentIndex + maxValueWithIndex);
20      
21        // Update `maxValueWithIndex` if the current spot, with the addition of its index, is greater than the current `maxValueWithIndex`
22        maxValueWithIndex = Math.max(maxValueWithIndex, values[currentIndex] + currentIndex);
23    }
24
25    // Return the highest score found among all pairs
26    return maxScore;
27}
28

Time and Space Complexity

The given code defines a method to find the maximum score of a sightseeing pair where the score is defined by the sum of the values of the pair reduced by the distance between them (i.e., values[i] + values[j] + i - j for a pair (i, j)).

Time Complexity

The time complexity of the code is O(n), where n is the length of the input list values.

This is because there is a single for-loop that goes through the array values from the second element to the last, doing constant time operations within the loop such as computing the maximum of ans and updating the value of mx. There are no nested loops or other operations that would increase the time complexity beyond linear time.

Space Complexity

The space complexity of the code is O(1).

There are only a few variables used (ans, mx, and j) and their memory consumption does not depend on the input size, which means that there is a constant amount of extra space used regardless of the size of values.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: