• Leetcode POTDs

Problem 1014 Best Sightseeing Pair

Problem Statement

Link - Problem 1014

Question

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 * 104
• 1 <= values[i] <= 1000

Solution

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

Complexity Analysis

| Algorithm             | Time Complexity | Space Complexity |
| --------------------- | --------------- | ---------------- |
| Two-pointer traversal | O(n)            | O(1)             |

Explanation

Intial Thoughts

The problem involves maximizing the score of a pair of sightseeing spots. The score is determined by adding the values of the two spots and subtracting the distance between them. This suggests that we need to balance the values of the spots with their distances. We could start by examining the relationship between the values and the distances. The distance is determined by the indices of the spots, so we may need to use the indices to our advantage. We could try to use a brute force approach, but given the constraints, this may not be efficient. A more efficient approach might involve using a sliding window or iterating through the array to find the optimal pair. The time complexity is O(n) and space complexity is O(1), so we should aim for a solution that meets these constraints.

Intuitive Analysis

One way to intuitively solve this problem is to think of it as a trade-off between the values of the spots and their distances. We want to maximize the total value while minimizing the distance. We can start by keeping track of the maximum left value (maxLeft) and updating it as we iterate through the array. The current score is determined by adding maxLeft to the current value and subtracting the distance. By keeping track of the maximum score, we can efficiently find the optimal pair without having to examine every pair. This approach allows us to balance the values and distances while meeting the time and space complexity requirements. By breaking down the problem into smaller sub-problems and solving them iteratively, we can find an efficient solution.

1. Intuition

• The problem can be solved by iterating through the array and maintaining the maximum score seen so far.
• The key insight is to realize that the score of a pair (i, j) can be rewritten as (values[i] + i) + (values[j] - j).
• This allows us to separate the problem into two parts: finding the maximum value of (values[i] + i) and the maximum value of (values[j] - j).
• However, we cannot simply find the maximum of these two values separately, because the indices i and j must be different.
• To solve this, we can maintain the maximum value of (values[i] + i) seen so far, and update it as we iterate through the array.
• We can then use this maximum value to calculate the maximum score of a pair (i, j).
• This approach works because it ensures that we are always considering the maximum possible score for each pair (i, j).
• It also has a time complexity of O(n), making it efficient for large inputs.

2. Implementation

• The solution initializes maxScore to 0 and maxLeft to values[0] + 0, which represents the maximum value of (values[i] + i) seen so far.
• The solution then iterates through the array, starting from the second element (j = 1).
• For each element, it updates maxScore to be the maximum of the current maxScore and the score of the pair (i, j), where i is the index of the maximum value of (values[i] + i) seen so far.
• The solution also updates maxLeft to be the maximum of the current maxLeft and the value of (values[j] + j).
• This is done using the line maxScore = max(maxScore, maxLeft + values[j] - j); and maxLeft = max(maxLeft, values[j] + j);.
• The solution finally returns maxScore, which represents the maximum score of a pair (i, j).
• The time complexity of the solution is O(n), where n is the length of the input array.
• The space complexity is O(1), as the solution only uses a constant amount of space to store the variables maxScore and maxLeft.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input array once, resulting in a linear time complexity. This is evident in the for loop for(int j = 1; j < n; j++), which visits each element in the array exactly once.
• The dominant operations within the loop are the comparisons and assignments, which occur in constant time. Therefore, the time complexity is not affected by the specific operations performed.
• The time complexity is classified as O(n) because the number of operations grows linearly with the size of the input. This is in line with the formal definition of Big O notation: the algorithm’s running time is bounded above by a constant times the input size, ignoring lower-order terms.

Space Complexity:

• The algorithm uses a constant amount of memory to store the variables maxScore, maxLeft, n, and j. This memory usage does not grow with the size of the input array.
• The only data structures used are a few integers, which have a fixed memory footprint. There are no arrays, linked lists, trees, or other data structures that would require additional memory proportional to the input size.
• Therefore, the space complexity is classified as O(1), indicating that the memory usage is constant and does not vary with the size of the input.

Footnote

This question is rated as Medium difficulty.

Hints

Can you tell the best sightseeing spot in one pass (ie. as you iterate over the input?) What should we store or keep track of as we iterate to do this?