Is Best Sightseeing Pair easy or hard?

Best Sightseeing Pair is considered a Medium difficulty problem. The main challenge is recognizing the algebraic transformation that separates the formula into two parts, enabling a linear-time solution.

Best Sightseeing Pair Python/Java solution

Python and Java implementations follow the same logic: iterate through the array, track the maximum values[i] + i, and update the result using values[j] - j at each step. The algorithm runs in O(n) time and uses constant extra memory.

How to solve Best Sightseeing Pair in O(n)?

Rewrite the formula values[i] + values[j] + i - j as (values[i] + i) + (values[j] - j). Traverse the array once while storing the maximum values[i] + i encountered so far. At each index j, compute the score using that maximum and update the result.

What is the best approach for Best Sightseeing Pair?

The optimal solution uses a single pass through the array while maintaining the maximum value of values[i] + i seen so far. For each index j, compute the candidate score as bestPrefix + values[j] - j. This reduces the problem to O(n) time and O(1) space.

Is Best Sightseeing Pair asked at Google/Amazon/Meta?

Best Sightseeing Pair is a common medium-level array optimization problem frequently appearing in technical interview preparation lists. Similar pattern questions involving prefix maximum tracking appear in interviews at companies like Amazon, Google, and Meta.

What data structure is used in Best Sightseeing Pair?

The optimized solution only requires the input array and a few variables to track the running maximum. No additional data structures like heaps or hash maps are necessary, making it a constant-space array optimization technique.

What is the time complexity of Best Sightseeing Pair?

The brute force approach runs in O(n^2) time because it checks every pair (i, j). The optimized approach runs in O(n) time with O(1) extra space by tracking the best prefix value values[i] + i during a single pass.

Description Hints 1 Solution Video 8:27

1014. Best Sightseeing Pair

Medium62.7% acceptance6 companies

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

Asked at 6 companies

Wayfair Nutanix

Google Bloomberg Amazon Meta

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

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?

8:27

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxScoreSightseeingPair(self, values: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[8,1,5,2,6]

Input

[1,2]

Your code is saved on this device.Solution