Best Sightseeing Pair solution and explanation
Google
9 more videos on this problem
Best Sightseeing Pair - Leetcode 1014 - PythonNeetCodeIO · 8:27 · 10K views
Best Sightseeing Pair | 3 Approaches | Detailed For Beginners | Leetcode 1014 | codestorywithMIKcodestorywithMIK · 26:36 · 8K views
Leetcode 1014. Best Sightseeing Pair #Dynamic ProgrammingCode with Alisha · 10:52 · 5K views
Best Sightseeing Pair | Leetcode 1014Techdose · 13:46 · 3K views
1014. Best Sightseeing Pair | One Pass | Prefix MaximumAryan Mittal · 10:48 · 1K views
Leetcode potd is back | 1014. Best Sightseeing Pair | dsa | shashcode | shashwatShashCode · 14:18 · 1K views
Best Sightseeing Pair | Leetcode - 1014Algorithms Made Easy · 13:54 · 513 views
LeetCode 1014 Best Sightseeing Pair | Array | DP | Asked in GoogleCode Harmony · 11:38 · 327 views
Leetcode 1014. Best Sightseeing PairElite Code · 27:57 · 311 views
Leetcode : 1014 - Best Sightseeing PairVarun Kumar · 9:16 · 166 views
The problem
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 * 1041 <= 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.
def maxScoreSightseeingPair(values):
max_score = 0
for i in range(len(values)):
for j in range(i + 1, len(values)):
score = values[i] + values[j] + i - j
max_score = max(max_score, score)
return max_score
values = [8, 1, 5, 2, 6]
print("Max Score:", maxScoreSightseeingPair(values))public class Solution {
public int maxScoreSightseeingPair(int[] values) {
int maxScore = 0;
for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {
int score = values[i] + values[j] + i - j;
maxScore = Math.max(maxScore, score);
}
}
return maxScore;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] values = {8, 1, 5, 2, 6};
System.out.println("Max Score: " + sol.maxScoreSightseeingPair(values));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxScoreSightseeingPair(vector<int>& values) {
int maxScore = 0;
int n = values.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int score = values[i] + values[j] + i - j;
maxScore = max(maxScore, score);
}
}
return maxScore;
}
int main() {
vector<int> values = {8, 1, 5, 2, 6};
cout << "Max Score: " << maxScoreSightseeingPair(values) << endl;
return 0;
}function maxScoreSightseeingPair(values) {
let maxScore = 0;
for (let i = 0; i < values.length; i++) {
for (let j = i + 1; j < values.length; j++) {
const score = values[i] + values[j] + i - j;
maxScore = Math.max(maxScore, score);
}
}
return maxScore;
}
const values = [8, 1, 5, 2, 6];
console.log("Max Score:", maxScoreSightseeingPair(values));#include <stdio.h>
int maxScoreSightseeingPair(int* values, int valuesSize){
int maxScore = 0;
for(int i = 0; i < valuesSize; i++) {
for(int j = i + 1; j < valuesSize; j++) {
int score = values[i] + values[j] + i - j;
if(score > maxScore) {
maxScore = score;
}
}
}
return maxScore;
}
int main() {
int values[] = {8, 1, 5, 2, 6};
int max_score = maxScoreSightseeingPair(values, 5);
printf("Max Score: %d\n", max_score);
return 0;
}using System;
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int maxScore = 0;
for (int i = 0; i < values.Length; i++) {
for (int j = i + 1; j < values.Length; j++) {
int score = values[i] + values[j] + i - j;
maxScore = Math.Max(maxScore, score);
}
}
return maxScore;
}
public static void Main(string[] args) {
int[] values = { 8, 1, 5, 2, 6 };
Solution sol = new Solution();
Console.WriteLine("Max Score: " + sol.MaxScoreSightseeingPair(values));
}
}The Python solution uses a double loop to consider each pair of sights, compute their score, and keep track of the maximum score using the 'max' function.
Time Complexity: O(n^2) given the nested iteration.
Space Complexity: O(1) as no additional structures are utilized.
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'.
def maxScoreSightseeingPair(values):
max_score = 0
max_i_val = values[0] + 0
for j in range(1, len(values)):
max_score = max(max_score, max_i_val + values[j] - j)
max_i_val = max(max_i_val, values[j] + j)
return max_score
values = [8, 1, 5, 2, 6]
print("Max Score:", maxScoreSightseeingPair(values))public class Solution {
public int maxScoreSightseeingPair(int[] values) {
int maxScore = 0;
int maxIValue = values[0] + 0;
for (int j = 1; j < values.length; j++) {
maxScore = Math.max(maxScore, maxIValue + values[j] - j);
maxIValue = Math.max(maxIValue, values[j] + j);
}
return maxScore;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] values = {8, 1, 5, 2, 6};
System.out.println("Max Score: " + sol.maxScoreSightseeingPair(values));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxScoreSightseeingPair(vector<int>& values) {
int maxScore = 0;
int maxIValue = values[0] + 0;
for (int j = 1; j < values.size(); ++j) {
maxScore = max(maxScore, maxIValue + values[j] - j);
maxIValue = max(maxIValue, values[j] + j);
}
return maxScore;
}
int main() {
vector<int> values = {8, 1, 5, 2, 6};
cout << "Max Score: " << maxScoreSightseeingPair(values) << endl;
return 0;
}function maxScoreSightseeingPair(values) {
let maxScore = 0;
let maxIValue = values[0] + 0;
for (let j = 1; j < values.length; j++) {
maxScore = Math.max(maxScore, maxIValue + values[j] - j);
maxIValue = Math.max(maxIValue, values[j] + j);
}
return maxScore;
}
const values = [8, 1, 5, 2, 6];
console.log("Max Score:", maxScoreSightseeingPair(values));#include <stdio.h>
int maxScoreSightseeingPair(int* values, int valuesSize){
int max_score = 0;
int max_i_val = values[0] + 0;
for (int j = 1; j < valuesSize; j++) {
max_score = (max_i_val + values[j] - j) > max_score ? (max_i_val + values[j] - j) : max_score;
max_i_val = (values[j] + j) > max_i_val ? (values[j] + j) : max_i_val;
}
return max_score;
}
int main() {
int values[] = {8, 1, 5, 2, 6};
int max_score = maxScoreSightseeingPair(values, 5);
printf("Max Score: %d\n", max_score);
return 0;
}using System;
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int maxScore = 0;
int maxIValue = values[0] + 0;
for (int j = 1; j < values.Length; j++) {
maxScore = Math.Max(maxScore, maxIValue + values[j] - j);
maxIValue = Math.Max(maxIValue, values[j] + j);
}
return maxScore;
}
public static void Main(string[] args) {
int[] values = {8, 1, 5, 2, 6};
Solution sol = new Solution();
Console.WriteLine("Max Score: " + sol.MaxScoreSightseeingPair(values));
}
}In Python, the solution leverages a single pass using a rolling 'values[i] + i' to compute the maximal score efficiently, updating the score with each index jump.
Time Complexity: O(n) since each element is considered once.
Space Complexity: O(1) as no additional data structures are used.
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).
function maxScoreSightseeingPair(values: number[]): number {
let [ans, mx] = [0, 0];
for (let j = 0; j < values.length; ++j) {
ans = Math.max(ans, mx + values[j] - j);
mx = Math.max(mx, values[j] + j);
}
return ans;
}func maxScoreSightseeingPair(values []int) (ans int) {
mx := 0
for j, x := range values {
ans = max(ans, mx+x-j)
mx = max(mx, x+j)
}
return
}impl Solution {
pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
let mut ans = 0;
let mut mx = 0;
for (j, &x) in values.iter().enumerate() {
ans = ans.max(mx + x - j as i32);
mx = mx.max(x + j as i32);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Approach | Time Complexity: O(n^2) given the nested iteration. |
| Approach 2: Optimized Single Pass | Time Complexity: O(n) since each element is considered once. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n^2) | O(1) | Useful for understanding the formula or validating correctness on small inputs |
| Optimized Single Pass | O(n) | O(1) | Best general solution for large arrays and the expected interview answer |
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.