Best Sightseeing Pair - Practice Coding Problems

Best Sightseeing Pair - Problem

You are given an integer array values where values[i] represents the value of the i^th 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.

Input & Output

Example 1 — Basic Case

$ Input: values = [8,1,5,2,6]

› Output: 11

💡 Note: Best pair is (i=0, j=2): values[0] + values[2] + 0 - 2 = 8 + 5 + 0 - 2 = 11

Example 2 — Adjacent Elements

$ Input: values = [1,2]

› Output: 2

💡 Note: Only one pair possible: values[0] + values[1] + 0 - 1 = 1 + 2 + 0 - 1 = 2

Example 3 — Large Distance Penalty

$ Input: values = [10,1,1,1,20]

› Output: 26

💡 Note: Best pair is (i=0, j=4): values[0] + values[4] + 0 - 4 = 10 + 20 + 0 - 4 = 26

Constraints

2 ≤ values.length ≤ 5 × 10⁴
1 ≤ values[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of sightseeing spot values [8,1,5,2,6]

Score Formula

score = values[i] + values[j] + i - j (distance penalty)

Find Maximum

Return the highest score among all pairs

Key Takeaway

🎯 Key Insight: Rewrite the formula to separate first and second spot contributions for optimal solution

Asked in

f Facebook 25 a Amazon 20 G Google 15

The key insight is rewriting the score formula as (values[i] + i) + (values[j] - j) to separate concerns. Track the maximum (values[i] + i) seen so far while scanning through j positions. Best approach uses one pass optimization with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all possible pairs and find maximum score
One Pass Optimization	O(n)	O(1)	Track the best first spot while scanning for second spots

Brute Force — Algorithm Steps

Step 1: Use nested loops to generate all pairs (i,j) where i < j
Step 2: Calculate score = values[i] + values[j] + i - j for each pair
Step 3: Track and return the maximum score found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Pairs

Create all pairs (i,j) where i < j

Calculate Scores

Compute values[i] + values[j] + i - j

Find Maximum

Track the highest score found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* values, int n) {
    int maxScore = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int score = values[i] + values[j] + i - j;
            if (score > maxScore) {
                maxScore = score;
            }
        }
    }
    
    return maxScore;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    int values[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        values[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(values, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all n*(n-1)/2 pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only use constant extra variables

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler