1014. Best Sightseeing Pair - Detailed Explanation

Problem Statement

Description:
You are given an array A where each element represents the score of a sightseeing spot. The score of a pair of sightseeing spots (i, j) with i < j is defined as:

$[\text{score}(i, j) = A[i] + A[j] + i - j]$

Your task is to return the maximum score of a pair of sightseeing spots.

Example 1:

Input: A = [8, 1, 5, 2, 6]
Output: 11
Explanation:
The best pair is (i=0, j=2), giving a score:
(8 + 5 + 0 - 2 = 11).

Example 2:

Input: A = [1, 3, 5]
Output: 6
Explanation:
The best pair is (i=1, j=2), with score:
(3 + 5 + 1 - 2 = 7). (Note: Different inputs may yield different optimal pairs. Verify by checking all possibilities.)

Constraints:

$(2 \leq A.length \leq 5 \times 10^4)$
$(1 \leq A[i] \leq 10^4)$

Intuition and Hints

Observation:
The score function can be re-written as:

$[A[i] + i + (A[j] - j)\]$

This split shows that if you fix an index (j), the best partner (i) is the one that maximizes (A[i] + i) for all (i < j).
Key Idea:
As you traverse the array, maintain the maximum value of (A[i] + i) seen so far. For each index (j), compute a candidate score:

$[\text{candidate} = (\text{max\_so\_far}) + A[j] - j]$

Update your answer if this candidate is larger than the current maximum, and then update the max-so-far value for the next iterations.
Efficiency:
A simple one-pass traversal of the array yields an O(n) solution which is efficient given the constraints.

Approaches

Approach 1: One-Pass Greedy Scan

Explanation:

Initialize:
- Set max_so_far to (A[0] + 0). This represents the best candidate for the left sightseeing spot.
- Set result to a very small value (or negative infinity).
Traverse the Array:
- For each index j from 1 to the end of the array:
  - Calculate the candidate score using the best (A[i] + i) seen so far:
    
    $[\text{candidate} = \text{max\_so\_far} + A[j] - j]$
  - Update result if the candidate score is higher than the current result.
  - Update max_so_far with:
    
    $[\text{max\_so\_far} = \max(\text{max\_so\_far}, A[j] + j)]$
Return Result:
- The maximum score computed during the traversal is the answer.

Python Code (One-Pass Greedy Scan):

Python3

. . . .

Java Code (One-Pass Greedy Scan):

Java

. . . .

Approach 2: Brute Force (For Understanding Only)

Explanation:

A brute force solution would check every possible pair ((i, j)) with (i < j) and compute the score $(A[i] + A[j] + i - j)$ . Then, you select the maximum score from all computed values.

Time Complexity: O(n²) – This approach is too slow for large inputs.
Use Case:
Although not practical for large arrays, this method helps understand the problem before optimizing.

Python Code (Brute Force):

Python3

. . . .

Java Code (Brute Force):

Java

. . . .

Complexity Analysis

One-Pass Greedy Scan Approach:
- Time Complexity: O(n) – We scan the array once.
- Space Complexity: O(1) – Only a few extra variables are used.
Brute Force Approach:
- Time Complexity: O(n²) – Checking every pair.
- Space Complexity: O(1) – Constant extra space.

Common Pitfalls & Edge Cases

Edge Cases:
- Arrays of length 2 (the only valid pair is the single pair available).
- Ensure the calculation correctly accounts for the index differences when computing (A[i] + i) and (A[j] - j).
Pitfalls:
- Forgetting to update the maximum value of (A[i] + i) as you traverse the array.
- Not handling cases where the maximum score is negative (though given the problem constraints with positive scores, this is unlikely).

TAGS

leetcode

CONTRIBUTOR

Design Gurus Team

GET YOUR FREE

Coding Questions Catalog