1014. Best Sightseeing Pair - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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