Jobs

Interviews

Discussions

Best Sightseeing Pair

Medium

Nutanix

0 views

Topics:

ArraysGreedy Algorithms

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.

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 * 10⁴
1 <= values[i] <= 1000

Try coding it in LeetCode

Best Sightseeing Pair

Medium

Nutanix

0 views

Topics:

ArraysGreedy Algorithms

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.

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 * 10⁴
1 <= values[i] <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array be empty, or contain only one element?
If there are multiple pairs that result in the same maximum sightseeing score, is any one of them acceptable?
Are the elements in the input array guaranteed to be integers?
What should I return if no pair exists (e.g., if the input is empty or contains only one element)?

Brute Force Solution

Approach

The brute force approach to finding the best sightseeing pair involves checking every single possible pair of locations. We want to find the pair that gives us the highest sightseeing score. This means trying every combination and comparing their scores.

Here's how the algorithm would work step-by-step:

Take the first location and consider it as the first location in our pair.
Now, consider every other location as the second location in our pair.
Calculate the sightseeing score for this pair of locations.
Remember the highest sightseeing score you've found so far.
Repeat the process, starting with the second location as the first location in the pair and then considering every other location as the second location.
Continue doing this until you have considered every location as the first location in the pair, combined with every other location as the second location.
After checking all pairs, the highest sightseeing score you remembered is the best one.

Code Implementation

def best_sightseeing_pair_brute_force(values):
    highest_sightseeing_score = 0

    # Iterate through each location as the first in the pair
    for first_location_index in range(len(values)): 
        for second_location_index in range(len(values)):

            # Ensure we are not comparing the same location to itself
            if first_location_index != second_location_index:
                
                sightseeing_score = values[first_location_index] + values[second_location_index] + first_location_index - second_location_index

                # Keep track of the largest score
                if sightseeing_score > highest_sightseeing_score:
                    highest_sightseeing_score = sightseeing_score

    return highest_sightseeing_score

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n locations in the input array. For each location, it then considers every other location as a potential pair, resulting in another inner loop that iterates up to n times in the worst case. This nested loop structure means that for each of the n locations, we are performing approximately n operations, leading to n * n operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach only uses a few constant space variables: one to store the highest sightseeing score found so far, and potentially a couple of index variables to iterate through the locations. No auxiliary data structures like arrays, lists, or hash maps are created. Therefore, the algorithm's space complexity is independent of the input size N, where N is the number of locations, and remains constant.

Optimal Solution

Approach

The core idea is to keep track of the best 'potential' starting point as we go. Instead of checking every possible pair, we efficiently update what the best first element of a pair could be, letting us maximize the score by pairing it with later elements.

Here's how the algorithm would work step-by-step:

Imagine you're walking through a list of locations and each location has a score.
As you walk, keep track of the best score you've seen so far, adjusted for how far you've walked.
At each location, calculate a combined score by adding the current location's score to your best score adjusted by the distance.
If this combined score is better than any you've seen before, remember it.
Also, at each location, check if this location itself is a better potential starting point for future pairs than the best starting point you've seen so far.
After looking at all the locations, the highest combined score you found is the best sightseeing score.

Code Implementation

def best_sightseeing_pair(values):
    max_combined_score = 0
    best_starting_score_so_far = values[0] + 0

    for index in range(1, len(values)): 
        #Calculate score of current location paired with best previous location.
        current_combined_score = best_starting_score_so_far + values[index] - index

        max_combined_score = max(max_combined_score, current_combined_score)

        # Check if the current location offers a better starting point.
        best_starting_score_so_far = max(best_starting_score_so_far, values[index] + index)

    return max_combined_score

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n, representing sightseeing locations, only once. Inside the loop, it performs a constant number of operations: updating the best potential starting point and calculating the combined sightseeing score. Therefore, the time complexity is directly proportional to the number of locations, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm keeps track of the best combined score seen so far and the best potential starting point. These are stored in a few variables. Since the number of these variables does not depend on the input size N (the number of locations), the auxiliary space used remains constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately since no valid pair can exist.
Array with only one element	Return 0 since a sightseeing pair requires at least two distinct elements.
Array with all identical values	The algorithm should correctly handle identical values and find the best pair among them.
Array with large indices causing integer overflow during calculation of score	Use long data type to prevent integer overflow when calculating the score (A[i] + A[j] + i - j).
Array with negative values	The problem statement doesn't restrict the input to positive integers, so the algorithm should handle negative values correctly.
Array with a very large number of elements (scaling considerations)	The provided greedy approach with O(n) time complexity is efficient and scales well with a large input array.
Array with extreme boundary values for integers (min/max int)	Ensure calculations A[i] + A[j] + i - j does not cause overflow/underflow using long data types.
Multiple pairs yield the same maximum score	The problem asks for the maximum score, and the algorithm will return one such score even if multiple pairs yield the same result, which is acceptable.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array be empty, or contain only one element?
If there are multiple pairs that result in the same maximum sightseeing score, is any one of them acceptable?
Are the elements in the input array guaranteed to be integers?
What should I return if no pair exists (e.g., if the input is empty or contains only one element)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first location and consider it as the first location in our pair.
Now, consider every other location as the second location in our pair.
Calculate the sightseeing score for this pair of locations.
Remember the highest sightseeing score you've found so far.
Repeat the process, starting with the second location as the first location in the pair and then considering every other location as the second location.
Continue doing this until you have considered every location as the first location in the pair, combined with every other location as the second location.
After checking all pairs, the highest sightseeing score you remembered is the best one.

Code Implementation

def best_sightseeing_pair_brute_force(values):
    highest_sightseeing_score = 0

    # Iterate through each location as the first in the pair
    for first_location_index in range(len(values)): 
        for second_location_index in range(len(values)):

            # Ensure we are not comparing the same location to itself
            if first_location_index != second_location_index:
                
                sightseeing_score = values[first_location_index] + values[second_location_index] + first_location_index - second_location_index

                # Keep track of the largest score
                if sightseeing_score > highest_sightseeing_score:
                    highest_sightseeing_score = sightseeing_score

    return highest_sightseeing_score

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're walking through a list of locations and each location has a score.
As you walk, keep track of the best score you've seen so far, adjusted for how far you've walked.
At each location, calculate a combined score by adding the current location's score to your best score adjusted by the distance.
If this combined score is better than any you've seen before, remember it.
Also, at each location, check if this location itself is a better potential starting point for future pairs than the best starting point you've seen so far.
After looking at all the locations, the highest combined score you found is the best sightseeing score.

Code Implementation

def best_sightseeing_pair(values):
    max_combined_score = 0
    best_starting_score_so_far = values[0] + 0

    for index in range(1, len(values)): 
        #Calculate score of current location paired with best previous location.
        current_combined_score = best_starting_score_so_far + values[index] - index

        max_combined_score = max(max_combined_score, current_combined_score)

        # Check if the current location offers a better starting point.
        best_starting_score_so_far = max(best_starting_score_so_far, values[index] + index)

    return max_combined_score

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately since no valid pair can exist.
Array with only one element	Return 0 since a sightseeing pair requires at least two distinct elements.
Array with all identical values	The algorithm should correctly handle identical values and find the best pair among them.
Array with large indices causing integer overflow during calculation of score	Use long data type to prevent integer overflow when calculating the score (A[i] + A[j] + i - j).
Array with negative values	The problem statement doesn't restrict the input to positive integers, so the algorithm should handle negative values correctly.
Array with a very large number of elements (scaling considerations)	The provided greedy approach with O(n) time complexity is efficient and scales well with a large input array.
Array with extreme boundary values for integers (min/max int)	Ensure calculations A[i] + A[j] + i - j does not cause overflow/underflow using long data types.
Multiple pairs yield the same maximum score	The problem asks for the maximum score, and the algorithm will return one such score even if multiple pairs yield the same result, which is acceptable.