Best Sightseeing Pair

MEDIUM

Description

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.

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

Approaches

Checkout 2 different approaches to solve Best Sightseeing Pair. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach involves checking every possible pair of sightseeing spots (i, j) where i < j. For each pair, it calculates the score and keeps track of the maximum score found so far. While simple to conceptualize, it is not efficient enough for the given constraints.

Algorithm

Initialize a variable maxScore to a very small number (or 0, since scores are positive).
Use a nested loop structure. The outer loop iterates with index i from 0 to n-2.
The inner loop iterates with index j from i+1 to n-1.
Inside the inner loop, calculate the score for the pair (i, j): currentScore = values[i] + values[j] + i - j.
Update maxScore if currentScore is greater: maxScore = max(maxScore, currentScore).
After both loops complete, return maxScore.

The brute-force method directly translates the problem statement into code. We use two nested loops to generate all valid pairs of indices (i, j) such that i is always less than j.

The outer loop selects the first sightseeing spot i, and the inner loop selects the second spot j from the remaining spots to the right. For each pair, we compute the score using the formula values[i] + values[j] + i - j. A variable, maxScore, is maintained throughout the process and is updated whenever a newly calculated score is higher than the current maxScore. After iterating through all possible pairs, maxScore will hold the highest possible score.

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int n = values.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentScore = values[i] + values[j] + i - j;
                maxScore = Math.max(maxScore, currentScore);
            }
        }
        return maxScore;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of sightseeing spots. The nested loops result in a quadratic number of score calculations, making it too slow for large N.Space Complexity: O(1), as it only uses a few variables to store the maximum score and loop indices, requiring constant extra space.

Pros and Cons

Pros:

Simple to understand and implement.
Correctly solves the problem for small input sizes.

Cons:

Highly inefficient due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for large inputs, such as the ones specified in the problem constraints.

Code Solutions

Checking out 3 solutions in different languages for Best Sightseeing Pair. Click on different languages to view the code.

class Solution {
public
  int maxScoreSightseeingPair(int[] values) {
    int ans = 0, mx = values[0];
    for (int j = 1; j < values.length; ++j) {
      ans = Math.max(ans, values[j] - j + mx);
      mx = Math.max(mx, values[j] + j);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Best Sightseeing Pair

Patterns:

Dynamic Programming

Data Structures:

Array

Companies:

Wayfair |