Maximum Strong Pair XOR I - Solution & Explanation
Problem Statement
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 = [5,6,25,30]
Output: 7
Explanation: There are 6 strong pairs in the array nums: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) and (30, 30).
The maximum XOR possible from these pairs is 25 XOR 30 = 7 since the only other non-zero XOR value is 5 XOR 6 = 3.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 100
Approach Overview
Problem Overview: You are given an integer array nums. A pair (x, y) is considered strong if |x - y| ≤ min(x, y). Among all valid strong pairs, compute the maximum value of x XOR y. The task is essentially filtering valid pairs based on the strong pair rule and maximizing the bitwise XOR result.
Approach 1: Brute Force with All Pair Checking (O(n²) time, O(1) space)
The most direct method checks every possible pair in the array. Use two nested loops and compute the condition |nums[i] - nums[j]| ≤ min(nums[i], nums[j]). If the pair satisfies the strong condition, compute nums[i] ^ nums[j] and track the maximum value. This works because the input size is small enough that evaluating all combinations is feasible. The approach relies only on basic array traversal and bit manipulation. Time complexity is O(n²) since every pair is checked, while space complexity remains O(1).
Approach 2: Optimized Search with Sorted Array (O(n log n + n²) time, O(1) space)
Sorting the array helps reduce unnecessary comparisons. After sorting, if nums[i] ≤ nums[j], the strong pair condition simplifies to nums[j] - nums[i] ≤ nums[i]. For each starting index i, expand a second pointer j while the condition holds. As soon as nums[j] - nums[i] > nums[i], further elements will also fail because the array is sorted. Within the valid window, compute XOR values and update the maximum. Sorting introduces O(n log n) overhead, but early termination reduces comparisons in practice. This technique mirrors patterns used in sliding window style scans where the valid range expands until a constraint breaks.
The sorted strategy also clarifies the structure of valid pairs: larger values can only pair with numbers not too far away in magnitude. That insight prevents scanning the entire remainder of the array for every element.
Recommended for interviews: Start with the brute force explanation. It proves you understand the definition of a strong pair and the XOR objective. Then propose the sorted approach to reduce unnecessary checks. Interviewers usually expect the brute force first because the constraints allow O(n²), but showing the sorted optimization demonstrates awareness of ordering tricks commonly used in array and sliding window problems.
Approach 1: Approach 1: Brute Force with All Pair Checking
This approach involves checking all possible pairs in the array and filtering those that satisfy the strong pair condition, then finding the maximum XOR from these pairs. This is feasible given the constraint of the problem that the array length is at most 50.
The solution defines a function maxStrongPairXOR that iterates over all pairs in the array while ensuring they form a strong pair. For such pairs, it calculates their XOR, and tracks the maximum XOR found.
Complexity
Time Complexity: O(n^2), where n is the length of the input array because we are checking all pairs.
Space Complexity: O(1) since no extra space proportional to input size is used.
Approach 2: Approach 2: Optimized Search with Sorted Array
This approach involves first sorting the array, which potentially allows for more efficient checking of the strong pair condition by only considering necessary pairs. Due to the sorted order, the condition |x - y| <= min(x, y) can often be more quickly evaluated with a two-pointer technique or similar strategy.
The array is sorted at the very beginning to potentially reduce the number of necessary comparisons when assessing which pairs can be considered strong pairs.
Complexity
Time Complexity: O(n^2) in worst case due to the pairwise comparison, but sorting helps in practice.
Space Complexity: O(1).
Approach 3: Enumeration
We can enumerate each pair of numbers (x, y) in the array. If |x - y| leq min(x, y), then this pair is a strong pair. We can calculate the XOR value of this pair and update the answer.
The time complexity is O(n^2), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Approach 4: Sorting + Binary Trie
Observing the inequality |x - y| leq min(x, y), which involves absolute value and minimum value, we can assume x leq y, then we have y - x leq x, that is, y leq 2x. We can enumerate y from small to large, then x must satisfy the inequality y leq 2x.
Therefore, we sort the array nums, and then enumerate y from small to large. We use two pointers to maintain a window so that the elements x in the window satisfy the inequality y leq 2x. We can use a binary trie to maintain the elements in the window, so we can find the maximum XOR value in the window in O(1) time. Each time we add y to the trie, and remove the elements at the left end of the window that do not satisfy the inequality, this can ensure that the elements in the window satisfy the inequality y leq 2x. Then query the maximum XOR value from the trie and update the answer.
The time complexity is O(n times log M), and the space complexity is O(n times log M). Here, n is the length of the array nums, and M is the maximum value in the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with All Pair Checking | Time Complexity: O(n^2), where n is the length of the input array because we are checking all pairs. |
| Approach 2: Optimized Search with Sorted Array | Time Complexity: O(n^2) in worst case due to the pairwise comparison, but sorting helps in practice. |
| Enumeration | — |
| Sorting + Binary Trie | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Small input sizes or when implementing the most direct solution |
| Sorted Array with Early Break | O(n log n + n²) | O(1) | When you want fewer comparisons by exploiting sorted order |
Video Solution
2932. Maximum Strong Pair XOR I (Leetcode Easy) • Programming Live with Larry • 631 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Maximum Strong Pair XOR I easy or hard?
Maximum Strong Pair XOR I Python/Java solution
How to solve Maximum Strong Pair XOR I in O(n)?
What is the best approach for Maximum Strong Pair XOR I?
Is Maximum Strong Pair XOR I asked at Google/Amazon/Meta?
What data structure is used in Maximum Strong Pair XOR I?
What is the time complexity of Maximum Strong Pair XOR I?
Ready to solve this problem?
Practice Maximum Strong Pair XOR I with our built-in code editor and test cases.
Practice on FleetCode