Watch 7 video solutions for Maximum Strong Pair XOR II, a hard level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Prakhar Agrawal has 1,894 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums. A pair of integers x and y is called a strong pair if it satisfies the condition:
|x - y| <= min(x, y)You need to select two integers from nums such that they form a strong pair and their bitwise XOR is the maximum among all strong pairs in the array.
Return the maximum XOR value out of all possible strong pairs in the array nums.
Note that you can pick the same integer twice to form a pair.
Example 1:
Input: nums = [1,2,3,4,5]
Output: 7
Explanation: There are 11 strong pairs in the array nums: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.
Example 2:
Input: nums = [10,100] Output: 0 Explanation: There are 2 strong pairs in the array nums: (10, 10) and (100, 100). The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.
Example 3:
Input: nums = [500,520,2500,3000] Output: 1020 Explanation: There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000). The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 220 - 1Problem Overview: You are given an array of integers and must find the maximum XOR value among all strong pairs. A pair (x, y) is strong if |x - y| ≤ min(x, y). The goal is to efficiently evaluate valid pairs and compute the maximum x ^ y without checking every combination.
Approach 1: Sort and Two Pointer Approach with Trie (O(n log M) time, O(n) space)
Sort the array first. When the array is sorted and x ≤ y, the strong pair condition becomes y - x ≤ x, which simplifies to y ≤ 2x. This property lets you maintain a valid range using a sliding window. Move the right pointer through the array and keep the left pointer adjusted so that all values inside the window satisfy the strong pair constraint.
Within the window, the goal becomes finding the maximum XOR between the current value and any earlier value. A binary Trie stores the bit representation of numbers currently in the window. Each insertion and query takes O(log M), where M is the maximum value in the array (number of bits). For every new element, query the trie for the best XOR partner, update the answer, then insert the number into the trie.
The two-pointer window guarantees that only valid strong pairs remain in the trie. When the left pointer moves forward, remove outdated elements from the trie. Sorting costs O(n log n), and each element is inserted and removed once, leading to overall O(n log M) operations.
Approach 2: Bit Manipulation Optimization (O(n log M) time, O(n) space)
This method builds the XOR result greedily from the most significant bit to the least significant bit using bit manipulation. Instead of a full trie structure, maintain prefix sets of numbers while iteratively testing whether a candidate bit can be set in the answer.
For each bit position, assume the current bit of the answer can be 1 and check if two prefixes exist that produce this XOR. While performing this check, enforce the strong pair condition using the same sorted order and window constraint y ≤ 2x. Hash sets store prefixes efficiently and allow constant-time lookups.
This approach reduces structural overhead compared to an explicit trie while still leveraging bitwise properties of XOR. The complexity remains O(n log M) because each bit position is evaluated across the array.
Recommended for interviews: The sorted two-pointer + trie solution is the most common explanation in interviews. It clearly separates the constraints: sorting enforces the strong pair condition via a sliding window, and the trie efficiently computes maximum XOR. Interviewers expect you to derive the y ≤ 2x transformation and combine it with a bitwise structure. The bit manipulation variant demonstrates deeper understanding of XOR optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Two Pointers + Trie | O(n log M) | O(n) | Best general solution. Efficiently maintains valid strong pairs and computes maximum XOR using a trie. |
| Bit Manipulation Prefix Optimization | O(n log M) | O(n) | Useful when optimizing XOR computation without an explicit trie structure. |