Best Sightseeing Pair

Medium
334.

Best Sightseeing Pair

Best Sightseeing Pair is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Uber and Nutanix interviews.

You are given an integer array values where values[i] is the value of the i-th sightseeing spot. Two spots i < j are j - i apart.

The score of a pair is values[i] + values[j] + i - j. Return the maximum score over all pairs.

Example 1

Input
values = [8,1,5,2,6]
Output
11
Explanation
Pairing spots 0 and 2: 8 + 5 + 0 - 2 = 11.

Example 2

Input
values = [1,2]
Output
2

Example 3

Input
values = [1,3,5]
Output
7

Constraints

  • 2 <= values.length <= 40
  • 1 <= values[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} values
 * @return {number}
 */
var maxScoreSightseeingPair = function(values) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Best Sightseeing Pair — Solution in Python, Java & C++

Best Sightseeing Pair solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Best Sightseeing Pair is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Uber and Nutanix interviews.

Problem statement

You are given an integer array values where values[i] is the value of the i-th sightseeing spot. Two spots i < j are j - i apart.

The score of a pair is values[i] + values[j] + i - j. Return the maximum score over all pairs.

Example 1

Input: values = [8,1,5,2,6]
Output: 11
Explanation: Pairing spots 0 and 2: 8 + 5 + 0 - 2 = 11.

Example 2

Input: values = [1,2]
Output: 2

Example 3

Input: values = [1,3,5]
Output: 7

Constraints

  • 2 <= values.length <= 40
  • 1 <= values[i] <= 1000

Hints for Best Sightseeing Pair

  1. Hint 1

    Split the score into a left part values[i] + i and a right part values[j] - j.

  2. Hint 2

    Scan left to right keeping the best left part seen so far, and pair it with the current right part.

  3. Hint 3

    That turns an O(n²) pair search into one pass.

How to solve Best Sightseeing Pair

Split the score into (values[i] + i) and (values[j] - j); sweep j keeping the best left part seen so far.

Approach

  1. Start bestLeft = values[0] + 0.
  2. For each j ≥ 1, update the answer with bestLeft + values[j] - j, then bestLeft = max(bestLeft, values[j] + j).
  3. Return the answer.

Why it works

The two halves of the score depend on i and j independently, so for each j the optimal i is the one maximising values[i] + i among earlier indices.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Update bestLeft after using it, so i < j is preserved.

Reference solution

Python

def maxScoreSightseeingPair(values) -> int:
    best = float("-inf")
    best_left = values[0]
    for j in range(1, len(values)):
        best = max(best, best_left + values[j] - j)
        best_left = max(best_left, values[j] + j)
    return best

Java

public static int maxScoreSightseeingPair(int[] values) {
    int best = -2000000, bestLeft = values[0];
    for (int j = 1; j < values.length; j++) {
        best = Math.max(best, bestLeft + values[j] - j);
        bestLeft = Math.max(bestLeft, values[j] + j);
    }
    return best;
}

C++

int maxScoreSightseeingPair(vector<int>& values) {
    int best = -2000000, bestLeft = values[0];
    for (int j = 1; j < (int) values.size(); j++) {
        best = max(best, bestLeft + values[j] - j);
        bestLeft = max(bestLeft, values[j] + j);
    }
    return best;
}

JavaScript

var maxScoreSightseeingPair = function(values) {
    let best = -Infinity, bestLeft = values[0];
    for (let j = 1; j < values.length; j++) {
        const candidate = bestLeft + values[j] - j;
        if (candidate > best) best = candidate;
        if (values[j] + j > bestLeft) bestLeft = values[j] + j;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming