Best Sightseeing Pair - Video Solutions

Problem Overview: You are given an array values where each index represents a sightseeing spot. The score of a pair (i, j) with i < j is defined as values[i] + values[j] + i - j. The task is to find the maximum possible score among all valid pairs.

Approach 1: Brute Force Approach (O(n²) time, O(1) space)

The direct method checks every possible pair of indices (i, j) where i < j. For each pair, compute the score using the formula and keep track of the maximum value seen so far. This requires two nested loops: the outer loop picks the first sightseeing spot, and the inner loop evaluates every possible second spot to the right. The approach is straightforward and useful for validating correctness, but it becomes slow for large inputs because it performs roughly n*(n-1)/2 comparisons.

Approach 2: Optimized Single Pass (O(n) time, O(1) space)

The key insight comes from rewriting the formula: values[i] + values[j] + i - j becomes (values[i] + i) + (values[j] - j). While scanning the array from left to right, you maintain the best value of values[i] + i seen so far. At each position j, compute the candidate score by combining this stored maximum with values[j] - j. After evaluating the pair, update the running maximum of values[i] + i. This transforms the problem into a single linear pass over the array. The idea resembles a rolling best-state update often seen in lightweight dynamic programming patterns.

Recommended for interviews: Start by explaining the brute force approach to show you understand the scoring formula and pair constraints. Then derive the optimized form by separating the expression into two independent components. Interviewers expect the O(n) single-pass solution because it demonstrates the ability to algebraically transform the formula and maintain a running optimum.