Jobs

Interviews

Discussions

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

Medium

Amazon

22 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given two integer arrays x and y, each of length n. You must choose three distinct indices i, j, and k such that:

x[i] != x[j]
x[j] != x[k]
x[k] != x[i]

Your goal is to maximize the value of y[i] + y[j] + y[k] under these conditions. Return the maximum possible sum that can be obtained by choosing such a triplet of indices.

If no such triplet exists, return -1.

Example 1:

Input: x = [1,2,1,3,2], y = [5,3,4,6,2]

Output: 14

Explanation:

Choose i = 0 (x[i] = 1, y[i] = 5), j = 1 (x[j] = 2, y[j] = 3), k = 3 (x[k] = 3, y[k] = 6).
All three values chosen from x are distinct. 5 + 3 + 6 = 14 is the maximum we can obtain. Hence, the output is 14.

Example 2:

Input: x = [1,2,1,2], y = [4,5,6,7]

Output: -1

Explanation:

There are only two distinct values in x. Hence, the output is -1.

Constraints:

n == x.length == y.length
3 <= n <= 10⁵
1 <= x[i], y[i] <= 10⁶

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

Medium

Amazon

22 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given two integer arrays x and y, each of length n. You must choose three distinct indices i, j, and k such that:

x[i] != x[j]
x[j] != x[k]
x[k] != x[i]

Your goal is to maximize the value of y[i] + y[j] + y[k] under these conditions. Return the maximum possible sum that can be obtained by choosing such a triplet of indices.

If no such triplet exists, return -1.

Example 1:

Input: x = [1,2,1,3,2], y = [5,3,4,6,2]

Output: 14

Explanation:

Choose i = 0 (x[i] = 1, y[i] = 5), j = 1 (x[j] = 2, y[j] = 3), k = 3 (x[k] = 3, y[k] = 6).
All three values chosen from x are distinct. 5 + 3 + 6 = 14 is the maximum we can obtain. Hence, the output is 14.

Example 2:

Input: x = [1,2,1,2], y = [4,5,6,7]

Output: -1

Explanation:

There are only two distinct values in x. Hence, the output is -1.

Constraints:

n == x.length == y.length
3 <= n <= 10⁵
1 <= x[i], y[i] <= 10⁶

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 are the possible ranges for values in the input array, and can they be negative?
What should I return if no triplet of distinct X-values exists?
Are the X-values guaranteed to be unique, or could there be duplicate X-values?
Is there a limit on the size of the input array?
When you say 'distinct X-values', are we considering distinct numerical values or distinct indices in the array?

Brute Force Solution

Approach

We're looking for the best group of three items from a list. The brute force way is to simply check every possible combination of three items. By considering every single possibility, we guarantee we'll find the best one.

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

First, grab any three items from the list.
Calculate the score (Y-sum) for this group of three.
Remember that score. That's our current best score.
Now, pick a different set of three items.
Calculate the score for this new group.
If this new score is better than the score we remembered, then forget the old score and remember this new, better score.
Keep doing this, picking every possible combination of three items and checking its score.
When you've tried every single combination of three items, the score you're remembering is the best possible score.

Code Implementation

def maximize_y_sum_brute_force(x_values, y_values):
    number_of_elements = len(x_values)
    best_y_sum = float('-inf')

    # Iterate through all possible combinations of three distinct x_values
    for first_index in range(number_of_elements):
        for second_index in range(first_index + 1, number_of_elements):
            for third_index in range(second_index + 1, number_of_elements):

                # Calculate the Y-sum for the current triplet
                current_y_sum = y_values[first_index] + y_values[second_index] + y_values[third_index]

                # Update the best Y-sum if the current Y-sum is greater
                if current_y_sum > best_y_sum:
                    best_y_sum = current_y_sum

    return best_y_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The provided solution iterates through all possible triplets of distinct X-values from a list of n items. To select a triplet, we essentially have three nested loops. The outermost loop iterates through n items, the second loop iterates through the remaining items (n-1), and the innermost loop iterates through the items remaining after the first two selections (n-2). This results in approximately n * (n-1) * (n-2) operations. Ignoring lower order terms and constant factors, this simplifies to O(n³).

Space Complexity

O(1) – The brute-force approach, as described, only requires storing the best score found so far and the score of the current triplet. These are constant-size variables (likely integers or floats). No auxiliary data structures that scale with the input size N (the size of the list) are used to store intermediate results or combinations. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The key to solving this efficiently is focusing on finding the three largest Y-values for different X-values quickly. We don't need to consider every single combination of three X-values. Instead, we can focus on pre-processing the data to make finding the largest Y-values much faster.

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

Go through all the pairs of X and Y values.
For each X-value, keep track of the three largest Y-values associated with it. If an X-value has fewer than three associated Y-values, track all of them.
Now, go through all possible triplets of *distinct* X-values.
For each triplet of X-values, calculate the sum of the *three largest* Y-values that you previously recorded for each of those X-values.
Keep track of the highest total sum you've found across all triplets.
After checking all possible combinations of distinct X-values, return the highest total sum you found. This is the maximized Y-sum.

Code Implementation

def maximize_y_sum(x_values, y_values):
    x_to_y_values = {}

    for i in range(len(x_values)): 
        x = x_values[i]
        y = y_values[i]
        if x not in x_to_y_values:
            x_to_y_values[x] = []
        x_to_y_values[x].append(y)

    # Sort Y-values in descending order to easily pick the largest.
    for x in x_to_y_values:
        x_to_y_values[x].sort(reverse=True)

    max_y_sum = float('-inf')
    distinct_x_values = list(x_to_y_values.keys())

    # Iterate through all possible triplets of distinct X-values.
    for i in range(len(distinct_x_values)): 
        for j in range(i + 1, len(distinct_x_values)): 
            for k in range(j + 1, len(distinct_x_values)): 
                x1 = distinct_x_values[i]
                x2 = distinct_x_values[j]
                x3 = distinct_x_values[k]

                # Get the top 3 Y-values for each X, or fewer if less exist.
                top_y_values_x1 = x_to_y_values[x1][:3]
                top_y_values_x2 = x_to_y_values[x2][:3]
                top_y_values_x3 = x_to_y_values[x3][:3]

                # Calculate the sum of the largest Y-values for the triplet.
                current_y_sum = sum(top_y_values_x1) + sum(top_y_values_x2) + sum(top_y_values_x3)

                # Update the maximum Y-sum if the current sum is larger.
                max_y_sum = max(max_y_sum, current_y_sum)

    # Handle the case where no triplets exist.
    if max_y_sum == float('-inf'):
        return 0

    return max_y_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The algorithm first iterates through the input of n (X, Y) pairs to store the top three Y-values for each distinct X-value. Then, it iterates through all possible triplets of distinct X-values. If there are k distinct X-values, this step involves choosing 3 X-values, resulting in a cost proportional to k choose 3, or k(k-1)(k-2)/6 which is O(k³). In the worst-case scenario, k is proportional to n, therefore the overall time complexity is O(n³).

Space Complexity

O(N) – The algorithm stores, for each distinct X-value, up to three of the largest associated Y-values. In the worst case, where all X-values are distinct, we would need to store three Y-values for each X. Thus, the auxiliary space used is proportional to the number of distinct X-values, which is at most N where N is the number of X, Y pairs in the input. Therefore the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 or an error code, depending on the problem statement, indicating no triplet exists.
Array with fewer than 3 elements	Return 0 or an error code, depending on the problem statement, as a triplet cannot be formed.
Array with duplicate x-values	The solution must select distinct x-values, potentially requiring preprocessing to remove duplicates or using a data structure that enforces uniqueness.
All y-values are negative	The algorithm should correctly identify the three x-values that yield the least negative (closest to zero) sum.
Integer overflow when summing y-values	Use a larger data type (e.g., long in Java/C++) to store the sum if the y-values can be large, or check for overflow during summation.
Large input array (scalability)	Optimize the solution for time complexity, potentially using sorting or hashing to avoid brute-force triplet enumeration.
No unique triplet exists due to identical y-values associated with different x-values.	Handle this case by selecting the first encountered triplet or returning all possible triplets if the problem statement requires it.
Input array contains zero values for y.	The algorithm should handle zeros correctly when summing, potentially prioritizing triplets containing zeros to maximize the sum.

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 are the possible ranges for values in the input array, and can they be negative?
What should I return if no triplet of distinct X-values exists?
Are the X-values guaranteed to be unique, or could there be duplicate X-values?
Is there a limit on the size of the input array?
When you say 'distinct X-values', are we considering distinct numerical values or distinct indices in the array?

Brute Force Solution

Approach

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

First, grab any three items from the list.
Calculate the score (Y-sum) for this group of three.
Remember that score. That's our current best score.
Now, pick a different set of three items.
Calculate the score for this new group.
If this new score is better than the score we remembered, then forget the old score and remember this new, better score.
Keep doing this, picking every possible combination of three items and checking its score.
When you've tried every single combination of three items, the score you're remembering is the best possible score.

Code Implementation

def maximize_y_sum_brute_force(x_values, y_values):
    number_of_elements = len(x_values)
    best_y_sum = float('-inf')

    # Iterate through all possible combinations of three distinct x_values
    for first_index in range(number_of_elements):
        for second_index in range(first_index + 1, number_of_elements):
            for third_index in range(second_index + 1, number_of_elements):

                # Calculate the Y-sum for the current triplet
                current_y_sum = y_values[first_index] + y_values[second_index] + y_values[third_index]

                # Update the best Y-sum if the current Y-sum is greater
                if current_y_sum > best_y_sum:
                    best_y_sum = current_y_sum

    return best_y_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through all the pairs of X and Y values.
For each X-value, keep track of the three largest Y-values associated with it. If an X-value has fewer than three associated Y-values, track all of them.
Now, go through all possible triplets of *distinct* X-values.
For each triplet of X-values, calculate the sum of the *three largest* Y-values that you previously recorded for each of those X-values.
Keep track of the highest total sum you've found across all triplets.
After checking all possible combinations of distinct X-values, return the highest total sum you found. This is the maximized Y-sum.

Code Implementation

def maximize_y_sum(x_values, y_values):
    x_to_y_values = {}

    for i in range(len(x_values)): 
        x = x_values[i]
        y = y_values[i]
        if x not in x_to_y_values:
            x_to_y_values[x] = []
        x_to_y_values[x].append(y)

    # Sort Y-values in descending order to easily pick the largest.
    for x in x_to_y_values:
        x_to_y_values[x].sort(reverse=True)

    max_y_sum = float('-inf')
    distinct_x_values = list(x_to_y_values.keys())

    # Iterate through all possible triplets of distinct X-values.
    for i in range(len(distinct_x_values)): 
        for j in range(i + 1, len(distinct_x_values)): 
            for k in range(j + 1, len(distinct_x_values)): 
                x1 = distinct_x_values[i]
                x2 = distinct_x_values[j]
                x3 = distinct_x_values[k]

                # Get the top 3 Y-values for each X, or fewer if less exist.
                top_y_values_x1 = x_to_y_values[x1][:3]
                top_y_values_x2 = x_to_y_values[x2][:3]
                top_y_values_x3 = x_to_y_values[x3][:3]

                # Calculate the sum of the largest Y-values for the triplet.
                current_y_sum = sum(top_y_values_x1) + sum(top_y_values_x2) + sum(top_y_values_x3)

                # Update the maximum Y-sum if the current sum is larger.
                max_y_sum = max(max_y_sum, current_y_sum)

    # Handle the case where no triplets exist.
    if max_y_sum == float('-inf'):
        return 0

    return max_y_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 or an error code, depending on the problem statement, indicating no triplet exists.
Array with fewer than 3 elements	Return 0 or an error code, depending on the problem statement, as a triplet cannot be formed.
Array with duplicate x-values	The solution must select distinct x-values, potentially requiring preprocessing to remove duplicates or using a data structure that enforces uniqueness.
All y-values are negative	The algorithm should correctly identify the three x-values that yield the least negative (closest to zero) sum.
Integer overflow when summing y-values	Use a larger data type (e.g., long in Java/C++) to store the sum if the y-values can be large, or check for overflow during summation.
Large input array (scalability)	Optimize the solution for time complexity, potentially using sorting or hashing to avoid brute-force triplet enumeration.
No unique triplet exists due to identical y-values associated with different x-values.	Handle this case by selecting the first encountered triplet or returning all possible triplets if the problem statement requires it.
Input array contains zero values for y.	The algorithm should handle zeros correctly when summing, potentially prioritizing triplets containing zeros to maximize the sum.