Problem Description

You have two integer arrays x and y, both with the same length n. Your task is to select three different indices i, j, and k from these arrays such that the values at these indices in array x are all different from each other. Specifically:

• x[i] ≠ x[j] (the value at index i must be different from the value at index j)
• x[j] ≠ x[k] (the value at index j must be different from the value at index k)
• x[k] ≠ x[i] (the value at index k must be different from the value at index i)

Once you find three indices that satisfy these conditions, you want to maximize the sum y[i] + y[j] + y[k] - the sum of the corresponding values from array y at those same three indices.

The goal is to find the maximum possible sum of three y values where their corresponding x values are all distinct. If it's impossible to find three indices where all the x values are different (for example, if array x has fewer than 3 unique values), return -1.

For example, if x = [1, 2, 3, 2] and y = [10, 20, 30, 40], you could choose indices 0, 1, and 2 since x[0] = 1, x[1] = 2, and x[2] = 3 are all different. This would give you a sum of y[0] + y[1] + y[2] = 10 + 20 + 30 = 60.

Intuition

To maximize the sum of three y values while ensuring their corresponding x values are all different, we need to be greedy - we want to pick the largest possible y values.

Think about it this way: if we want the maximum sum, we should prioritize selecting indices with the highest y values. The constraint is that the x values at these indices must all be different from each other.

This leads us to a greedy strategy: sort all pairs (x[i], y[i]) by their y values in descending order. Then, we can iterate through this sorted list and pick the first three pairs that have distinct x values.

Why does this work? Because we're processing pairs in order of decreasing y values, the first three pairs we find with distinct x values will automatically give us the maximum possible sum. Any other combination would involve replacing at least one of our selected y values with a smaller one (since we're going through them in descending order), which would decrease the total sum.

The key insight is that we don't need to check all possible combinations of three indices. By sorting and greedily selecting from the top, we guarantee we're getting the best possible sum. We use a hash set to keep track of which x values we've already used, ensuring we only pick distinct ones.

If we go through the entire sorted list and can't find three distinct x values, it means the problem has no valid solution, so we return -1.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a sorting and greedy approach with a hash table to track selected values:

1. Create pairs and sort: First, we pair up the elements from arrays x and y into a 2D array arr where each element is a tuple (x[i], y[i]). We then sort this array in descending order based on the y values using arr.sort(key=lambda x: -x[1]). The negative sign ensures descending order.

2. Initialize tracking variables: We create a hash set vis to keep track of which x values we've already selected, and initialize ans = 0 to accumulate the sum of selected y values.

3. Greedy selection: We iterate through the sorted arr:

   • For each pair (a, b) where a is the x value and b is the y value
   • Check if a is already in our vis set (meaning we've already used this x value)
   • If a is already used, skip to the next pair with continue
   • If a hasn't been used, add it to vis and add its corresponding b value to our running sum ans

4. Check completion: After adding each new value, we check if len(vis) == 3, meaning we've successfully found three distinct x values. If so, we immediately return ans as our maximum sum.

5. Handle invalid case: If the loop completes without finding three distinct x values (the array doesn't have enough unique x values), we return -1.

The time complexity is O(n log n) due to sorting, and the space complexity is O(n) for storing the paired array and the hash set. The greedy approach guarantees optimality because we're always selecting the highest available y values that satisfy our constraint of having distinct x values.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• x = [1, 2, 1, 3, 2]
• y = [50, 40, 30, 60, 20]

Step 1: Create pairs and sort by y values (descending)

First, we pair up the elements:

• (1, 50) from index 0
• (2, 40) from index 1
• (1, 30) from index 2
• (3, 60) from index 3
• (2, 20) from index 4

After sorting by y values in descending order:

• (3, 60) - highest y value
• (1, 50)
• (2, 40)
• (1, 30)
• (2, 20) - lowest y value

Step 2: Initialize tracking variables

• vis = {} (empty set to track used x values)
• ans = 0 (sum accumulator)

Step 3: Greedy selection

Iteration 1: Process (3, 60)

• x value = 3, not in vis
• Add 3 to vis: vis = {3}
• Add 60 to sum: ans = 60
• Check: len(vis) = 1 (need more values)

Iteration 2: Process (1, 50)

• x value = 1, not in vis
• Add 1 to vis: vis = {3, 1}
• Add 50 to sum: ans = 110
• Check: len(vis) = 2 (need one more)

Iteration 3: Process (2, 40)

• x value = 2, not in vis
• Add 2 to vis: vis = {3, 1, 2}
• Add 40 to sum: ans = 150
• Check: len(vis) = 3 ✓

Step 4: Return result We found three distinct x values (3, 1, 2) with the maximum possible sum of their corresponding y values: 60 + 50 + 40 = 150.

Note that we didn't need to check (1, 30) or (2, 20) because we already found our optimal solution. Even though these pairs exist, using them would require replacing one of our selected values with a smaller y value, which would decrease the total sum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this algorithm is the sorting step. The code creates a list of tuples from the two input arrays and sorts them based on the second element (y values) in descending order using arr.sort(key=lambda x: -x[1]). This sorting operation has a time complexity of O(n × log n) where n is the length of the input arrays. The subsequent iteration through the sorted array takes O(n) time in the worst case, but since it terminates early when 3 distinct elements are found, it's at most O(n). The overall time complexity is therefore O(n × log n).

Space Complexity: O(n)

The algorithm creates additional data structures that contribute to space complexity:

• The arr list containing tuples of (x[i], y[i]) pairs requires O(n) space
• The vis set stores at most 3 elements (since the function returns when the set size reaches 3), which is O(1) in terms of the problem constraints
• The sorting operation may use additional O(log n) space for the sorting algorithm's recursion stack (depending on the implementation)

The overall space complexity is O(n) as the array of tuples dominates the space usage.

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

Common Pitfalls

Pitfall 1: Assuming indices must be consecutive or ordered

A common misunderstanding is thinking that the three indices i, j, and k must be in some specific order (like i < j < k) or must be consecutive. The problem actually allows any three different indices in any order.

Why this matters: If you incorrectly add ordering constraints, you might miss the optimal solution. For example, with x = [1, 2, 3] and y = [30, 10, 20], the optimal indices are (0, 2, 1) giving sum 60, not (0, 1, 2) giving sum 60 in this case, but in other cases the order could matter significantly.

Solution: The provided approach correctly handles this by considering all elements regardless of their original index positions after sorting.

Pitfall 2: Not handling duplicate x values properly

The most critical pitfall is incorrectly handling cases where the same x value appears multiple times with different y values. Consider x = [1, 1, 2, 3] and y = [100, 10, 20, 30].

Why this matters: You might be tempted to keep multiple pairs with the same x value, but the constraint requires all three selected x values to be distinct. The greedy approach must select only ONE occurrence of each unique x value - specifically, the one with the highest y value.

Solution: The code correctly handles this by:

1. Sorting pairs by y values in descending order
2. Using a set to track already-selected x values
3. Skipping any pair whose x value has already been selected

Pitfall 3: Early termination without checking feasibility

Some might try to optimize by taking the first three elements from the sorted array without checking if their x values are distinct.

Example problematic code:

# WRONG APPROACH
pairs.sort(key=lambda pair: -pair[1])
return pairs[0][1] + pairs[1][1] + pairs[2][1]  # Doesn't check x values!

Why this matters: With x = [1, 1, 1, 2] and y = [100, 90, 80, 10], this would incorrectly return 270 (100+90+80) even though all three top y values correspond to the same x value (1).

Solution: The provided code correctly checks each x value against the set of already-selected values before including it in the sum.

Pitfall 4: Not returning -1 for insufficient unique values

Forgetting to handle the case where there are fewer than 3 unique x values in the entire array.

Why this matters: With x = [1, 1, 2, 2] and y = [10, 20, 30, 40], there are only 2 unique x values (1 and 2), making it impossible to select 3 distinct ones.

Solution: The code correctly returns -1 when the loop completes without finding 3 distinct x values.