LeetCode 1014 - Best Sightseeing Pair

The problem presents an array of integers values, where each element represents the attractiveness or value of a sightseeing spot. The task is to find a pair of spots (i, j) with i < j such that the score values[i] + values[j] + i - j is maximized.

leetcodemediumarraydynamic-programming

LeetCode Problem 1014

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem presents an array of integers values, where each element represents the attractiveness or value of a sightseeing spot. The task is to find a pair of spots (i, j) with i < j such that the score values[i] + values[j] + i - j is maximized. In other words, the score is the sum of the two spot values minus the distance between them.

The input array can be as long as 50,000 elements, and each element ranges from 1 to 1000. This means any solution that tries to check all possible pairs (which would take O(n²) time) is too slow. The problem guarantees at least two elements in the array, so we do not have to handle empty arrays or arrays of length 1.

Key points to note include that negative distances reduce the score, so picking spots that are far apart decreases the score unless the values are very high. Edge cases could include arrays where all elements are equal, strictly increasing, strictly decreasing, or arrays with the maximum allowed length.

Approaches

The brute-force approach involves iterating over all possible pairs (i, j) with i < j, calculating values[i] + values[j] + i - j for each pair, and keeping track of the maximum score found. While this guarantees correctness because it checks all possibilities, it is O(n²) in time complexity and becomes infeasible for large arrays (up to 50,000 elements).

The optimal approach relies on a key observation. The score formula can be rewritten as:

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

This shows that the score is the sum of two components: values[i] + i (dependent on the first index) and values[j] - j (dependent on the second index). Thus, for each j, we only need the maximum value of values[i] + i for all previous i < j. We can maintain this maximum while iterating through the array once, achieving O(n) time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Iterates over all pairs (i, j)
Optimal O(n) O(1) Tracks the running maximum of values[i] + i

Algorithm Walkthrough

  1. Initialize a variable max_score to a very small number, such as negative infinity, to store the maximum score found.
  2. Initialize max_i_value as values[0] + 0 since the first element is the starting candidate for i.
  3. Iterate through the array starting from j = 1 to the end.
  4. For each j, calculate the potential score as max_i_value + values[j] - j. This represents pairing j with the best previous i.
  5. Update max_score if this potential score is higher than the current max_score.
  6. Update max_i_value if values[j] + j is greater than the current max_i_value. This ensures the best candidate i is always considered for the next iterations.
  7. After the loop completes, return max_score.

Why it works: By maintaining the invariant max_i_value = max(values[i] + i) for all i < j, we guarantee that each j is paired with the best possible previous i. This ensures the global maximum score is found without checking all pairs.

Python Solution

from typing import List

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        max_score = float('-inf')
        max_i_value = values[0] + 0
        
        for j in range(1, len(values)):
            max_score = max(max_score, max_i_value + values[j] - j)
            max_i_value = max(max_i_value, values[j] + j)
        
        return max_score

This implementation initializes the maximum score to negative infinity and max_i_value with the first element's contribution. For each subsequent element, it calculates the score using the best previous i, updates the maximum if needed, and updates the best i for future calculations. This avoids nested loops and achieves linear time complexity.

Go Solution

func maxScoreSightseeingPair(values []int) int {
    maxScore := -1 << 31
    maxIValue := values[0]
    
    for j := 1; j < len(values); j++ {
        maxScore = max(maxScore, maxIValue + values[j] - j)
        maxIValue = max(maxIValue, values[j] + j)
    }
    
    return maxScore
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

In Go, we initialize maxScore to a very small integer value and maxIValue with the first element. The loop calculates the potential score for each j and updates both the maximum score and maxIValue. The helper function max is used to simplify comparisons.

Worked Examples

Example 1: values = [8,1,5,2,6]

j max_i_value values[j] score = max_i_value + values[j] - j max_score
1 8 1 8 + 1 - 1 = 8 8
2 8 5 8 + 5 - 2 = 11 11
3 8 2 8 + 2 - 3 = 7 11
4 8 6 8 + 6 - 4 = 10 11

Final max_score = 11.

Example 2: values = [1,2]

j max_i_value values[j] score = max_i_value + values[j] - j max_score
1 1 2 1 + 2 - 1 = 2 2

Final max_score = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array, updating max values
Space O(1) Only two variables are maintained regardless of array size

The linear time complexity is achieved because we only track the best i value dynamically, avoiding nested loops. Constant space is used since no extra arrays or data structures are needed.

Test Cases

# test cases
assert Solution().maxScoreSightseeingPair([8,1,5,2,6]) == 11  # example 1
assert Solution().maxScoreSightseeingPair([1,2]) == 2  # example 2
assert Solution().maxScoreSightseeingPair([1000,1000,1000,1000]) == 1999  # all same values
assert Solution().maxScoreSightseeingPair([1,2,3,4,5]) == 6  # strictly increasing
assert Solution().maxScoreSightseeingPair([5,4,3,2,1]) == 7  # strictly decreasing
assert Solution().maxScoreSightseeingPair([1,1000,1,1000,1]) == 2000  # alternating high values
assert Solution().maxScoreSightseeingPair([1,1]) == 1  # minimum size
Test Why
[8,1,5,2,6] validates typical input with mixed values
[1,2] minimal input size
[1000,1000,1000,1000] all equal elements
[1,2,3,4,5] strictly increasing values
[5,4,3,2,1] strictly decreasing values
[1,1000,1,1000,1] alternating high and low values
[1,1] edge case of smallest allowed array

Edge Cases

Minimum Length Array: Arrays of length 2 are the smallest allowed. The implementation correctly handles this by starting the loop at index 1 and initializing max_i_value with index 0.

Large Values Array: Arrays with the maximum length and large values may lead to integer overflow in languages with fixed-size integers. Python handles this natively, while in Go, standard 32-bit integers can suffice given the constraints, but the initialization uses a safe minimum value.

Strictly Increasing/Decreasing Arrays: If the array is strictly increasing or decreasing, the optimal pair may involve the first element and last element. The algorithm correctly maintains the running maximum for i and considers all pairs efficiently.

This ensures robustness across a wide variety of input patterns.