Taro Logo

Best Sightseeing Pair

Medium
Amazon logo
Amazon
2 views
Topics:
Arrays

You are given an integer array values where values[i] represents the value of the i-th 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.

For example:

  • values = [8, 1, 5, 2, 6] should return 11, because i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
  • values = [1, 2] should return 2.

Could you provide an efficient algorithm to solve this problem?

Solution


Brute Force Solution

The naive solution involves checking all possible pairs of sightseeing spots (i, j) where i < j and calculating the score for each pair. Then, we return the maximum score found.

def max_sightseeing_pair_brute_force(values):
    max_score = 0
    n = len(values)
    for i in range(n):
        for j in range(i + 1, n):
            score = values[i] + values[j] + i - j
            max_score = max(max_score, score)
    return max_score

Time Complexity

O(n^2), where n is the number of sightseeing spots, because we have nested loops.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Solution

We can optimize the solution by realizing that the score can be expressed as values[i] + values[j] + i - j. We can rearrange this to (values[i] + i) + (values[j] - j). Therefore, we want to maximize values[i] + i for each i and values[j] - j for each j > i.

We can iterate through the values array, keeping track of the maximum value of values[i] + i encountered so far. For each j, we can calculate the score using the maximum values[i] + i and values[j] - j, and update the maximum score accordingly.

def max_sightseeing_pair_optimal(values):
    max_score = 0
    max_i_plus_i = values[0] + 0
    n = len(values)
    for j in range(1, n):
        score = max_i_plus_i + values[j] - j
        max_score = max(max_score, score)
        max_i_plus_i = max(max_i_plus_i, values[j] + j)
    return max_score

Time Complexity

O(n), where n is the number of sightseeing spots, as we iterate through the array once.

Space Complexity

O(1), as we only use a constant amount of extra space.

Edge Cases

  • Empty Input: The problem statement specifies that the length of values is between 2 and 5 * 10^4, so we don't need to handle an empty input.
  • Small Input (n=2): The algorithm should work correctly for the minimum allowed input size.
  • Large Values: The values of values[i] are between 1 and 1000, so we don't need to worry about integer overflow.