Best Sightseeing Pair

Best Sightseeing Pair

What is this problem about?

The "Best Sightseeing Pair interview question" is an optimization problem involving an array of "values" for different locations. A pair of locations $(i, j)$ with $i < j$ has a score defined as values[i] + values[j] + i - j. This formula accounts for the beauty of both spots (values[i] + values[j]) but penalizes the score based on the distance between them (j - i). You need to find the maximum possible score.

Why is this asked in interviews?

Meta and Amazon ask the "Best Sightseeing Pair coding problem" to evaluate a candidate's ability to rewrite an objective function to enable a single-pass solution. It’s a classic example of how to turn an $O(N^2)$ brute force into an $O(N)$ linear scan. It tests "Dynamic Programming" and "Array interview pattern" skills.

Algorithmic pattern used

This problem uses Function Decomposition and Linear Scanning. The formula values[i] + values[j] + i - j can be split into two parts:

• Part A (depends only on $i$): values[i] + i
• Part B (depends only on $j$): values[j] - j As you iterate through the array at index $j$, you want to find the largest values[i] + i encountered so far (where $i < j$).

1. Maintain a variable max_left representing the best values[i] + i.
2. For each $j$, update the total maximum: max_score = max(max_score, max_left + values[j] - j).
3. Update max_left for the next iteration: max_left = max(max_left, values[j] + j).

Example explanation

Values: [8, 1, 5, 2]

• $j = 0$: max_left = $8 + 0 = 8$.
• $j = 1$: Score = $8 + 1 - 1 = 8$. max_left = $max(8, 1 + 1) = 8$.
• $j = 2$: Score = $8 + 5 - 2 = 11$. max_left = $max(8, 5 + 2) = 8$.
• $j = 3$: Score = $8 + 2 - 3 = 7$. Max Score = 11.

Common mistakes candidates make

• $O(N^2)$ Brute Force: Using nested loops to check every pair, which fails for large arrays.
• Incorrect Split: Trying to find the max of values[i] and then subtracting distance later, which doesn't account for the fact that a slightly smaller values[i] that is closer to $j$ might be better.
• One-Pass Confusion: Forgetting to update max_left after calculating the score for the current $j$ (ensures $i < j$).

Interview preparation tip

Whenever you see a formula like A[i] + A[j] + (some relationship between i and j), try to group the terms so that each part depends on only one variable. This is the key to converting many "pair" problems into linear "running maximum" problems.