Scale Engineer

Best Sightseeing Pair

Med
#0968Time: 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: O(1), as it only uses a few variables to store the maximum score and loop indices, requiring constant extra space.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Wayfair

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as it only uses a few variables to store the maximum score and loop indices, requiring constant extra space.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem