Domain 2MediumMEDIUM

Best Sightseeing Pair

Iterate through the array maintaining max(values[i] + i) to calculate score for current j, achieving O(N) time and space.

Domain: medium•Updated: 2026-09-06
#greedy#array#O(n)#O(1)

Problem Breakdown

We need to find two indices i and j such that 0≤i<j<n0 \le i < j < n. The goal is to maximize the score defined by: score=values[i]+values[j]+(i−j)\text{score} = \text{values}[i] + \text{values}[j] + (i - j)

Inputs: An integer array values of length at least 2.
Outputs: A single integer representing the maximum possible score.

Implicit Constraints & Edge Cases:

  • Indices: We must strictly enforce i<ji < j. This means we cannot pair an element with itself or a previous index as the second part of the pair if it violates order (though mathematically handled by iteration direction).
  • Values: Values are positive (11 to 10001000), but indices can be up to 50,000. The term (i−j)(i - j) is always negative or zero since j>ij > i. This means the distance penalty reduces the score significantly as elements get further apart.
  • Overflow: With values ≤1000\le 1000 and length ≤5×104\le 5 \times 10^4, the maximum possible sum fits comfortably within a standard 32-bit integer, but Python handles arbitrary precision integers anyway. No special overflow handling needed in Python.

Intuition

A naive approach would be to iterate through all pairs (i,j)(i, j) and calculate the score for each pair.

  • Brute Force Complexity: O(n2)O(n^2). With n=50,000n = 50,000, this results in roughly 1.25×1091.25 \times 10^9 operations, which will exceed time limits (typically ∼108\sim 10^8 ops/sec).

Key Insight: Variable Separation. Let’s rearrange the score formula to separate terms dependent on i and terms dependent on j: score=(values[i]+i)+(values[j]−j)\text{score} = (\text{values}[i] + i) + (\text{values}[j] - j)

Notice that for a fixed current index acting as j, we want to maximize the first part (values[i]+i)(\text{values}[i] + i) among all valid previous indices i<ji < j. The second part (values[j]−j)(\text{values}[j] - j) is constant once we are at index j.

Optimal Strategy: As we iterate through the array from left to right, every element can act as a potential candidate for position i (the first spot) or position j (the second spot). We maintain a running maximum of (values[k]+k)(\text{values}[k] + k) seen so far. When we reach index j, we calculate the score using that stored maximum and update our global result.

Approach

  1. Initialize a variable, say max_i_val, to store values[i]+i\text{values}[i] + i for all valid i<ji < j. Start with index 0: max_i_val = values[0].
  2. Initialize ans (maximum score found so far) to the smallest possible integer or calculate it using the first pair (0,1)(0, 1) explicitly if needed. A safe initialization is negative infinity.
  3. Iterate through the array starting from index j=1j=1.
  4. At each step:
    • Calculate potential current score: current_score = max_i_val + values[j] - j.
    • Update global maximum: ans = max(ans, current_score).
    • Prepare for next iteration by updating the best first element seen so far: max_i_val = max(max_i_val, values[j] + j). Note that we update this using jj because in future iterations (where new index is k>jk > j), the current jj can become a valid candidate for position ii.
  5. Return ans after loop completion.

Complexity Analysis

  • Time Complexity: O(n)O(n), where nn is the length of values. We traverse the array exactly once with constant-time operations inside the loop.
  • Space Complexity: O(1)O(1). We only use a few integer variables regardless of input size.

Edge Cases Handled

  • Minimum Length: The code handles len(values) == 2 correctly by initializing with index 0 and iterating starting at index 1 (one iteration).
  • Decreasing Values: If values decrease rapidly, the distance penalty (i−j)(i-j) might outweigh value gains. The algorithm naturally selects pairs that balance this trade-off via max_i_val.
  • Single Valid Pair: Since we initialize with j=0j=0 logic and loop from 1, if only one pair exists (array size 2), it calculates exactly once before returning.

Solution

from typing import List

def maxScoreSightseeingPair(values: List[int]) -> int:
    # Constraints guarantee len(values) >= 2
    
    # Initialize best_i_val with values[0] + 0 (i=0 case for the first element)
    max_i_val = values[0] 
    
    ans = float('-inf')

    for j in range(1, len(values)):
        # Calculate score using the best previous 'i' and current 'j'
        # Formula rearranged: (values[i] + i) + (values[j] - j)
        current_score = max_i_val + values[j] - j
        
        if current_score > ans:
            ans = current_score
            
        # Update the best candidate for position 'i' seen so far.
        # Current index 'j' can now be an 'i' for future indices acting as 'k'.
        val_plus_idx = max_i_val + (values[j] - values[0]) if False else 0
        
        # Correct logic update: compare current j's potential i-value with stored best
        candidate_next_i = values[j] + j
        if candidate_next_i > max_i_val:
            max_i_val = candidate_next_i
            
    return ans

# Alternative concise implementation using Python's built-in functions logic implicitly, 
# but the explicit loop above is clearer for interview explanation.