Facebook Pixel

1014. Best Sightseeing Pair

MediumArrayDynamic Programming
Leetcode Link

Problem Description

You have an array values where each element values[i] represents the value of a sightseeing spot at position i.

When visiting two sightseeing spots at positions i and j (where i < j), you need to consider both their values and the distance between them. The distance between spots i and j is simply j - i.

The score for visiting a pair of spots (i, j) is calculated as: values[i] + values[j] + i - j. This formula adds the values of both spots, then adjusts for their positions by adding i and subtracting j.

Your task is to find the maximum possible score among all valid pairs of sightseeing spots.

For example, if you have spots at positions i = 1 and j = 4 with values values[1] = 8 and values[4] = 5, the score would be 8 + 5 + 1 - 4 = 10.

The key insight is that the score formula values[i] + values[j] + i - j can be rearranged as (values[i] + i) + (values[j] - j). This allows us to track the maximum value of values[i] + i seen so far as we iterate through the array, then for each position j, calculate the score using the best previous position.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

Looking at the score formula values[i] + values[j] + i - j, we need to find the maximum value across all valid pairs where i < j. A brute force approach would check all possible pairs, but this would be inefficient.

The key observation is that we can rearrange the formula by grouping terms related to each index: values[i] + values[j] + i - j = (values[i] + i) + (values[j] - j)

This rearrangement reveals that for any fixed position j, the score depends on two independent parts:

  • A term from position i: values[i] + i
  • A term from position j: values[j] - j

Since we want to maximize the total score for each j, we should pair it with the position i (where i < j) that has the maximum value of values[i] + i.

This leads to an efficient approach: as we iterate through the array from left to right, we can:

  1. Keep track of the maximum value of values[i] + i seen so far (this represents the best left position)
  2. For each position j, calculate the score using this maximum value plus values[j] - j
  3. Update our running maximum of values[i] + i to include the current position for future iterations

This way, we only need a single pass through the array, checking each position once as a potential right endpoint j, while maintaining the best possible left endpoint i we've seen so far.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using a single pass enumeration approach with two tracking variables:

  1. Initialize tracking variables:

    • ans: Stores the maximum score found so far, initialized to 0
    • mx: Tracks the maximum value of values[i] + i seen so far, initialized to 0

  2. Enumerate through the array: We iterate through each position j from left to right using enumerate(values) to get both the index and value.

  3. For each position j:

    • Calculate the score: Using the current position as the right endpoint, we compute the score as mx + x - j, where:

      • mx represents the best values[i] + i from all previous positions
      • x is values[j] (the current value)
      • The formula mx + x - j equals (values[i] + i) + (values[j] - j) for the best previous i

    • Update the maximum score: Compare the calculated score with ans and keep the larger value: ans = max(ans, mx + x - j)

    • Update mx for future iterations: After using position j as a right endpoint, we consider it as a potential left endpoint for future positions. Update mx to be the maximum of its current value and x + j (which is values[j] + j): mx = max(mx, x + j)

  4. Return the result: After processing all positions, ans contains the maximum score among all valid pairs.

The algorithm maintains the invariant that at each step j, mx contains the maximum value of values[i] + i for all i < j, ensuring we always pair each right endpoint with the optimal left endpoint. This achieves O(n) time complexity with O(1) space complexity.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with values = [8, 1, 5, 2, 6].

We want to find the maximum score where score = values[i] + values[j] + i - j for i < j.

Initial State:

  • ans = 0 (maximum score found)
  • mx = 0 (maximum of values[i] + i seen so far)

Iteration 1 (j=0, value=8):

  • Calculate score using j=0 as right endpoint: mx + 8 - 0 = 0 + 8 - 0 = 8
  • Update ans = max(0, 8) = 8
  • Update mx = max(0, 8 + 0) = 8 (now j=0 can be a left endpoint for future positions)

Iteration 2 (j=1, value=1):

  • Calculate score with best left endpoint (i=0): mx + 1 - 1 = 8 + 1 - 1 = 8
    • This represents the pair (0,1) with score: values[0] + values[1] + 0 - 1 = 8 + 1 + 0 - 1 = 8
  • Update ans = max(8, 8) = 8
  • Update mx = max(8, 1 + 1) = 8

Iteration 3 (j=2, value=5):

  • Calculate score with best left endpoint: mx + 5 - 2 = 8 + 5 - 2 = 11
    • This represents the pair (0,2) with score: values[0] + values[2] + 0 - 2 = 8 + 5 + 0 - 2 = 11
  • Update ans = max(8, 11) = 11
  • Update mx = max(8, 5 + 2) = 8

Iteration 4 (j=3, value=2):

  • Calculate score with best left endpoint: mx + 2 - 3 = 8 + 2 - 3 = 7
  • Update ans = max(11, 7) = 11
  • Update mx = max(8, 2 + 3) = 8

Iteration 5 (j=4, value=6):

  • Calculate score with best left endpoint: mx + 6 - 4 = 8 + 6 - 4 = 10
  • Update ans = max(11, 10) = 11
  • Update mx = max(8, 6 + 4) = 10

Result: The maximum score is 11, achieved by the pair (0,2).

We can verify: values[0] + values[2] + 0 - 2 = 8 + 5 - 2 = 11 ✓

The key insight is that mx always maintains the best possible left endpoint value (values[i] + i) for any future right endpoint, allowing us to find the optimal pair in a single pass.

Solution Implementation

1class Solution:
2    def maxScoreSightseeingPair(self, values: List[int]) -> int:
3        # Initialize the maximum score and the maximum value of (values[i] + i) seen so far
4        max_score = 0
5        max_left_value = 0
6      
7        # Iterate through each position j in the array
8        for j, value_j in enumerate(values):
9            # Calculate score for current j paired with the best i seen so far
10            # Score = (values[i] + i) + (values[j] - j)
11            # where max_left_value represents the best (values[i] + i) for all i < j
12            current_score = max_left_value + value_j - j
13            max_score = max(max_score, current_score)
14          
15            # Update the maximum (values[i] + i) for future j values
16            # This j could potentially be the best i for future iterations
17            max_left_value = max(max_left_value, value_j + j)
18      
19        return max_score
20
1class Solution {
2    public int maxScoreSightseeingPair(int[] values) {
3        // Initialize the maximum score and the maximum value of (values[i] + i) seen so far
4        int maxScore = 0;
5        int maxLeftValue = 0;
6      
7        // Iterate through each position j as the right endpoint of the pair
8        for (int j = 0; j < values.length; j++) {
9            // Calculate score for current pair: (values[i] + i) + (values[j] - j)
10            // where maxLeftValue represents the best (values[i] + i) for all i < j
11            maxScore = Math.max(maxScore, maxLeftValue + values[j] - j);
12          
13            // Update the maximum value of (values[i] + i) for future iterations
14            // This represents the best left endpoint value seen so far
15            maxLeftValue = Math.max(maxLeftValue, values[j] + j);
16        }
17      
18        return maxScore;
19    }
20}
21
1class Solution {
2public:
3    int maxScoreSightseeingPair(vector<int>& values) {
4        int maxScore = 0;      // Maximum score found so far
5        int maxLeft = 0;       // Maximum value of (values[i] + i) seen so far
6      
7        // Iterate through each position j as the right endpoint of the pair
8        for (int j = 0; j < values.size(); ++j) {
9            // Calculate score with current j and best previous i
10            // Score = values[i] + i + values[j] - j
11            // We already have max(values[i] + i) stored in maxLeft
12            maxScore = max(maxScore, maxLeft + values[j] - j);
13          
14            // Update the maximum left value for future iterations
15            // This represents the best potential left endpoint seen so far
16            maxLeft = max(maxLeft, values[j] + j);
17        }
18      
19        return maxScore;
20    }
21};
22
1/**
2 * Finds the maximum score of a sightseeing pair where score = values[i] + values[j] + i - j
3 * where i < j. This can be rewritten as (values[i] + i) + (values[j] - j).
4 * 
5 * @param values - Array of values representing the worth of each sightseeing spot
6 * @returns The maximum score achievable from any valid pair
7 */
8function maxScoreSightseeingPair(values: number[]): number {
9    // Initialize the maximum score found so far
10    let maxScore: number = 0;
11  
12    // Track the maximum value of (values[i] + i) seen so far
13    // This represents the best starting point for a pair ending at current j
14    let maxStartValue: number = 0;
15  
16    // Iterate through each potential ending position j
17    for (let j = 0; j < values.length; j++) {
18        // Calculate score if we pair the best starting point with current j
19        // Score = (values[i] + i) + (values[j] - j)
20        maxScore = Math.max(maxScore, maxStartValue + values[j] - j);
21      
22        // Update the best starting value for future iterations
23        // Consider if current position would be a better starting point
24        maxStartValue = Math.max(maxStartValue, values[j] + j);
25    }
26  
27    return maxScore;
28}
29

Time and Space Complexity

The time complexity is O(n), where n is the length of the array values. This is because the algorithm iterates through the array exactly once using a single for loop, performing constant-time operations (max comparisons and arithmetic operations) at each iteration.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size, storing just three variables: ans, mx, and the loop variables j and x. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Operations

Pitfall: A common mistake is updating max_left_value before calculating the current score. This would incorrectly allow pairing position j with itself.

Incorrect Implementation:

for j, value_j in enumerate(values):
    # WRONG: Updating max_left_value first
    max_left_value = max(max_left_value, value_j + j)
    current_score = max_left_value + value_j - j  # This could use j paired with itself!
    max_score = max(max_score, current_score)

Why it's wrong: If we update max_left_value first, when calculating the score for position j, we might be using values[j] + j as the left value, effectively pairing j with itself, which violates the constraint i < j.

Solution: Always calculate the score first, then update max_left_value:

for j, value_j in enumerate(values):
    # Calculate score BEFORE updating max_left_value
    current_score = max_left_value + value_j - j
    max_score = max(max_score, current_score)
    # Update max_left_value AFTER using j as right endpoint
    max_left_value = max(max_left_value, value_j + j)

2. Misunderstanding the Score Formula

Pitfall: Incorrectly implementing the score calculation by not properly decomposing the formula.

Incorrect Implementation:

# WRONG: Trying to track values[i] - i instead of values[i] + i
max_left_value = values[0] - 0
for j in range(1, len(values)):
    current_score = max_left_value + values[j] + j  # Wrong formula!
    max_score = max(max_score, current_score)
    max_left_value = max(max_left_value, values[j] - j)

Solution: Remember that the score formula values[i] + values[j] + i - j decomposes into (values[i] + i) + (values[j] - j). Track values[i] + i as the left component, not values[i] - i.

3. Edge Case Handling

Pitfall: Not handling arrays with only 2 elements or initializing variables incorrectly.

Incorrect Implementation:

# WRONG: Starting from index 1 without proper initialization
max_left_value = values[0] + 0
max_score = 0
for j in range(1, len(values)):  # What if we miss valid pairs?
    current_score = max_left_value + values[j] - j
    max_score = max(max_score, current_score)
    max_left_value = max(max_left_value, values[j] + j)

Solution: Initialize both max_score and max_left_value to 0, then process all elements including index 0. This ensures the algorithm works correctly even when the first element isn't part of the optimal pair:

max_score = 0
max_left_value = 0
for j, value_j in enumerate(values):
    current_score = max_left_value + value_j - j
    max_score = max(max_score, current_score)
    max_left_value = max(max_left_value, value_j + j)
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More