We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Best Sightseeing Pair

Difficulty: Medium

Problem Description

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.

Key Insights

  • The score of a pair of sightseeing spots combines values and their indices.
  • The formula can be rearranged to focus on maximizing a combination of values and indices.
  • The problem can be solved in a single pass using a greedy approach to keep track of the best score.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a greedy approach. We will maintain a variable to track the maximum score found so far and another variable to keep the best value of the sightseeing spot adjusted by its index. We iterate through the array, calculating the score for each potential pair by referencing the best previous value seen so far. This allows us to compute the maximum score efficiently in linear time without using extra space for a secondary data structure.

Code Solutions

def maxScoreSightseeingPair(values):
    max_score = 0
    max_i_value = values[0]  # This will store the best value + index seen so far
    
    for j in range(1, len(values)):
        # Calculate the score using the best previous value
        max_score = max(max_score, max_i_value + values[j] - j)
        # Update the best value + index for the next iteration
        max_i_value = max(max_i_value, values[j] + j)
    
    return max_score
← Back to All Questions