Skip to main content
Talentd

Best Sightseeing Pair - Solution & Explanation

MediumArrayDynamic Programming14 min readAsked at: Amazon, Meta, Google +3
Practice this problem

Problem Statement

You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

 

Example 1:

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

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

 

Constraints:

  • 2 <= values.length <= 5 * 104
  • 1 <= values[i] <= 1000

Approach Overview

Problem Overview: You are given an array values where each index represents a sightseeing spot. The score of a pair (i, j) with i < j is defined as values[i] + values[j] + i - j. The task is to find the maximum possible score among all valid pairs.

Approach 1: Brute Force Approach (O(n2) time, O(1) space)

The direct method checks every possible pair of indices (i, j) where i < j. For each pair, compute the score using the formula and keep track of the maximum value seen so far. This requires two nested loops: the outer loop picks the first sightseeing spot, and the inner loop evaluates every possible second spot to the right. The approach is straightforward and useful for validating correctness, but it becomes slow for large inputs because it performs roughly n*(n-1)/2 comparisons.

Approach 2: Optimized Single Pass (O(n) time, O(1) space)

The key insight comes from rewriting the formula: values[i] + values[j] + i - j becomes (values[i] + i) + (values[j] - j). While scanning the array from left to right, you maintain the best value of values[i] + i seen so far. At each position j, compute the candidate score by combining this stored maximum with values[j] - j. After evaluating the pair, update the running maximum of values[i] + i. This transforms the problem into a single linear pass over the array. The idea resembles a rolling best-state update often seen in lightweight dynamic programming patterns.

Recommended for interviews: Start by explaining the brute force approach to show you understand the scoring formula and pair constraints. Then derive the optimized form by separating the expression into two independent components. Interviewers expect the O(n) single-pass solution because it demonstrates the ability to algebraically transform the formula and maintain a running optimum.

Approach 1: Approach 1: Brute Force Approach

This approach iterates through each index in the array as a starting point and computes the score for every subsequent point. It keeps track of the maximum score found.

Although simple, this approach involves nested iteration, making it inefficient for large inputs due to the O(n^2) time complexity.

The solution uses a nested loop to brute-force calculate the score for each pair of sights (i < j). The outer loop fixes 'i' while the inner loop iterates over 'j', calculates the respective score, and updates the maximum score found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to the nested loops.
Space Complexity: O(1) as no additional space is used.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Single Pass

This approach is a much more efficient O(n) solution. It maintains a running maximal value of 'values[i] + i' to maximize the score of subsequent elements. As the array is traversed, it calculates and continuously updates the maximum possible score using this running maximum and 'values[j] - j'.

This optimized C solution iterates through the array, maintaining the maximal 'values[i] + i' seen so far and computing the current potential maximum score with 'values[j] - j'. The highest score is updated dynamically.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) since it makes a single pass.
Space Complexity: O(1) because additional space isn't used.

Try this approach in the editor →

Approach 3: Enumeration

We can enumerate j from left to right while maintaining the maximum value of values[i] + i for elements to the left of j, denoted as mx. For each j, the maximum score is mx + values[j] - j. The answer is the maximum of these maximum scores for all positions.

The time complexity is O(n), where n is the length of the array values. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force Approach

Time Complexity: O(n^2) due to the nested loops.
Space Complexity: O(1) as no additional space is used.

Approach 2: Optimized Single Pass

Time Complexity: O(n) since it makes a single pass.
Space Complexity: O(1) because additional space isn't used.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair EnumerationO(n^2)O(1)Useful for understanding the formula or validating correctness on small inputs
Optimized Single PassO(n)O(1)Best general solution for large arrays and the expected interview answer

Video Solution

Best Sightseeing Pair - Leetcode 1014 - Python • NeetCodeIO • 10,581 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Best Sightseeing Pair easy or hard?
Best Sightseeing Pair is considered a Medium difficulty problem. The main challenge is recognizing the algebraic transformation that separates the formula into two parts, enabling a linear-time solution.
Best Sightseeing Pair Python/Java solution
Python and Java implementations follow the same logic: iterate through the array, track the maximum values[i] + i, and update the result using values[j] - j at each step. The algorithm runs in O(n) time and uses constant extra memory.
How to solve Best Sightseeing Pair in O(n)?
Rewrite the formula values[i] + values[j] + i - j as (values[i] + i) + (values[j] - j). Traverse the array once while storing the maximum values[i] + i encountered so far. At each index j, compute the score using that maximum and update the result.
What is the best approach for Best Sightseeing Pair?
The optimal solution uses a single pass through the array while maintaining the maximum value of values[i] + i seen so far. For each index j, compute the candidate score as bestPrefix + values[j] - j. This reduces the problem to O(n) time and O(1) space.
Is Best Sightseeing Pair asked at Google/Amazon/Meta?
Best Sightseeing Pair is a common medium-level array optimization problem frequently appearing in technical interview preparation lists. Similar pattern questions involving prefix maximum tracking appear in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Best Sightseeing Pair?
The optimized solution only requires the input array and a few variables to track the running maximum. No additional data structures like heaps or hash maps are necessary, making it a constant-space array optimization technique.
What is the time complexity of Best Sightseeing Pair?
The brute force approach runs in O(n^2) time because it checks every pair (i, j). The optimized approach runs in O(n) time with O(1) extra space by tracking the best prefix value values[i] + i during a single pass.

Ready to solve this problem?

Practice Best Sightseeing Pair with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays