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:

  1. 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).
  2. 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)]

  3. Return Result:

    • The maximum score computed during the traversal is the answer.

Python Code (One-Pass Greedy Scan):

Python3
Python3

. . . .

Java Code (One-Pass Greedy Scan):

Java
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
Python3

. . . .

Java Code (Brute Force):

Java
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

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;