Best Sightseeing Pair: Decomposing the Score Formula

You are given an array of integers values where values[i] represents the value of the i-th sightseeing spot. The score of a pair (i, j) where i < j is values[i] + values[j] + i - j. Your task is to find the maximum score. This is LeetCode 1014: Best Sightseeing Pair.

Example: values = [8, 1, 5, 2, 6] returns 11 from the pair (0, 2): 8 + 5 + 0 - 2 = 11.

Why this problem matters

The brute force approach checks every pair (i, j), computing the score for each one. That is O(n^2), and with arrays up to 50,000 elements long, it will not pass. The problem is really asking: can you see through the formula to find a way to evaluate it in linear time?

This is a textbook example of formula decomposition, a technique where you split a combined expression into independent parts that can be optimized separately. The same idea appears in problems involving distances, costs, and weighted pairs. Once you recognize that a formula can be broken into a term that depends only on i and a term that depends only on j, you unlock the ability to sweep once through the array and track a running optimum.

The decomposition pattern here is closely related to Kadane's algorithm for maximum subarray. In Kadane's, you maintain a running best as you iterate and decide at each step whether to extend or restart. Here, you maintain a running maximum of one term while evaluating the other. Both rely on the same core idea: at each position, you only need the best thing you have seen so far, not a record of everything.

The key insight

The score formula is values[i] + values[j] + i - j. Rearrange the terms by grouping everything that depends on i together and everything that depends on j together:

score = (values[i] + i) + (values[j] - j)

This decomposition is the entire trick. For a fixed j, you want to maximize the score by choosing the best i (where i < j). The (values[j] - j) part is fixed once you know j. So to maximize the total, you need the largest (values[i] + i) for any i < j.

You do not need to search backward through all previous indices. Just keep a running maximum of (values[i] + i) as you sweep j from left to right. At each step, compute the candidate score as max_i + (values[j] - j), update the global best if this candidate is better, then update max_i to include the current index (since future values of j could pair with the current index as i).

This reduces the problem from O(n^2) pair checking to a single O(n) pass.

The solution

def max_score_sightseeing_pair(values):
    max_i = values[0] + 0
    best = 0
    for j in range(1, len(values)):
        best = max(best, max_i + values[j] - j)
        max_i = max(max_i, values[j] + j)
    return best

Here is what each piece does:

1. Initialize max_i to values[0] + 0. Before scanning, the only candidate for the left element is index 0, and its contribution is values[0] + 0.
2. Loop j from 1 to n-1. At each step, j is the right element of the pair.
3. Compute the candidate score: max_i + values[j] - j. This pairs the best left element seen so far with the current right element.
4. Update best if the candidate score exceeds the current best.
5. Update max_i: after using j as the right element, it becomes a candidate left element for future iterations. If values[j] + j is larger than the current max_i, update it.

The order of the two updates matters. You must compute the score before updating max_i, because i must be strictly less than j. If you updated max_i first, you would be allowing i == j, which violates the constraint.

Visual walkthrough

The walkthrough shows that max_i stays at 8 (from index 0) throughout the entire scan. Index 0 has such a strong values[i] + i score that no later index overtakes it. The best pairing happens at j=2, where values[2] - 2 = 3 combines with max_i = 8 to give 11.

Complexity analysis

Time is O(n) because you make a single pass through the array. At each index, you do a constant number of comparisons and arithmetic operations.

Space is O(1) because you only store two variables: max_i (the running maximum of values[i] + i) and best (the global best score). No auxiliary arrays or data structures are needed.

The building blocks

1. Formula decomposition

The core technique is algebraic manipulation of the score formula. You start with values[i] + values[j] + i - j and rewrite it as (values[i] + i) + (values[j] - j). This is not a deep mathematical insight. It is simple regrouping. But recognizing when to apply it is the skill.

The general pattern: if a pair-score formula f(i, j) can be written as g(i) + h(j) where g depends only on i and h depends only on j, then you can optimize over all pairs in O(n) time. For each j, the best score is max(g(i) for i < j) + h(j). Track the running max of g(i) and you are done.

This pattern shows up in distance problems, cost allocation problems, and any scenario where you want to pair elements and the pair score has separable terms.

2. Running maximum tracking

Once you have decomposed the formula, you need to efficiently query "what is the maximum g(i) for all i I have seen so far?" The answer is a single variable that you update at each step.

running_max = initial_value
for j in range(start, end):
    use running_max  # best g(i) for i < j
    running_max = max(running_max, g(j))  # j becomes candidate i

This is the same pattern used in Best Time to Buy and Sell Stock (track the minimum price seen so far) and Maximum Subarray (track the best subarray ending here). The variable names change, but the structure is identical: maintain a running optimum, use it, then update it.

Edge cases

• Two elements: only one pair exists, so return values[0] + values[1] - 1. The formula reduces to the sum minus 1 since i=0 and j=1.
• Decreasing values: when values drop sharply, the distance penalty (i - j) may dominate. The optimal pair might be adjacent rather than far apart. The algorithm handles this naturally because max_i gets updated at each step.
• All same values: if every element is the same value v, the score for adjacent pairs is 2*v - 1. Pairs farther apart score lower because the i - j penalty grows. The best pair is always adjacent, and the algorithm correctly finds score 2*v - 1.
• Large array: with up to 50,000 elements, O(n^2) brute force means 2.5 billion operations. The O(n) decomposition handles it effortlessly in a single pass.
• Values of 1: the minimum value is 1, so the minimum possible score for an adjacent pair is 1 + 1 + i - (i+1) = 1. The score is always positive since values are at least 1.

Common mistakes

1. Updating max_i before computing the score. If you write max_i = max(max_i, values[j] + j) before best = max(best, max_i + values[j] - j), you allow i == j. This gives an invalid pair. Always compute the score first, then update max_i.

2. Initializing best to a negative number. Since all values are at least 1 and there are at least 2 elements, the score is always positive. Initializing best = 0 works fine. But if you initialize it to float('-inf') that also works. What does not work is forgetting to handle the first pair entirely.

3. Not seeing the decomposition. Many people try to use two pointers or sliding windows, neither of which naturally applies here. The problem is fundamentally about algebraic rearrangement. If you find yourself reaching for complex data structures, step back and look at the formula.

From understanding to recall

You have seen the decomposition: split values[i] + values[j] + i - j into (values[i] + i) + (values[j] - j), then sweep with a running max. The idea is clean and the code is five lines. Understanding it takes minutes.

But reproducing it under interview pressure is a different skill. You need to remember that the formula splits cleanly, that you track max_i as a running maximum, and that the update order matters. These details slip away if you only read about them once.

Spaced repetition bridges this gap. You practice writing the decomposition and the single-pass loop from scratch at increasing intervals. After a few rounds, the pattern locks in. You see a pair-score optimization and the decomposition comes automatically: group by index, track the running max, sweep once. No fumbling, no second-guessing the update order.

The formula decomposition pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning each one in isolation and drilling it with spaced repetition is far more effective than grinding random problems and hoping the insight sticks.

Related posts

• Maximum Subarray - Kadane's algorithm uses the same running-max approach to avoid checking all subarrays
• Best Time to Buy and Sell Stock - Track a running minimum while iterating to find the best profit pair
• Maximum Product Subarray - Another decomposition trick where you track running min and max simultaneously

CodeBricks breaks the best sightseeing pair problem into its formula decomposition and running maximum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a pair-score optimization question shows up in your interview, you do not think about it. You just write it.