Maximum Strong Pair XOR I solution and explanation
8 more videos on this problem
2932. Maximum Strong Pair XOR I (Leetcode Easy)Programming Live with Larry · 2:07 · 631 views
100120. Maximum Strong Pair XOR I | Leetcode Weekly Contest 371 | Solution Code.Optimization · 0:11 · 596 views
2932. Maximum Strong Pair XOR ICP Geeks · 7:10 · 522 views
2932. Maximum Strong Pair XOR I | Brute Force | Weekly 371Tech Courses · 3:59 · 325 views
2932. Maximum Strong Pair XOR I #leetcode #leetcodechallengeCodeVia · 1:52 · 192 views
LeetCode 2932. Maximum Strong Pair XOR IYuki Kitayama · 13:37 · 183 views
Maximum Strong Pair XOR I | Leetcode Weekly Contest 371 | DCC NIT-ADCC NITA · 2:50 · 138 views
LeetCode Easy | #2932. Maximum Strong Pair XOR I | Time O(n²), Space O(1)Andrei Dobysh · 9:07 · 43 views
LeetCode 2932 | Maximum Strong Pair XOR I 🔥 Explained | Bit Manipulation DSANextGen Coders · 8:16 · 10 views
The problem
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.
def maxStrongPairXOR(nums):
max_xor = float('-inf')
for i in range(len(nums)):
for j in range(i, len(nums)):
x, y = nums[i], nums[j]
if abs(x - y) <= min(x, y):
max_xor = max(max_xor, x ^ y)
return max_xor
nums = [1, 2, 3, 4, 5]
print(maxStrongPairXOR(nums))public class StrongPairXOR {
public static int maxStrongPairXOR(int[] nums) {
int maxXOR = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int x = nums[i];
int y = nums[j];
if (Math.abs(x - y) <= Math.min(x, y)) {
maxXOR = Math.max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
System.out.println(maxStrongPairXOR(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int maxStrongPairXOR(vector<int>& nums) {
int maxXOR = INT_MIN;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i; j < nums.size(); ++j) {
int x = nums[i];
int y = nums[j];
if (abs(x - y) <= min(x, y)) {
maxXOR = max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
cout << maxStrongPairXOR(nums) << endl;
return 0;
}function maxStrongPairXOR(nums) {
let maxXOR = -Infinity;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
let x = nums[i], y = nums[j];
if (Math.abs(x - y) <= Math.min(x, y)) {
maxXOR = Math.max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
let nums = [1, 2, 3, 4, 5];
console.log(maxStrongPairXOR(nums));#include <stdio.h>
#include <limits.h>
int maxStrongPairXOR(int* nums, int numsSize) {
int maxXOR = INT_MIN;
for (int i = 0; i < numsSize; ++i) {
for (int j = i; j < numsSize; ++j) {
int x = nums[i];
int y = nums[j];
if (abs(x - y) <= (x < y ? x : y)) {
int xorValue = x ^ y;
if (xorValue > maxXOR) {
maxXOR = xorValue;
}
}
}
}
return maxXOR;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxStrongPairXOR(nums, size));
return 0;
}using System;
public class StrongPairXOR {
public static int MaxStrongPairXOR(int[] nums) {
int maxXOR = int.MinValue;
for (int i = 0; i < nums.Length; i++) {
for (int j = i; j < nums.Length; j++) {
int x = nums[i];
int y = nums[j];
if (Math.Abs(x - y) <= Math.Min(x, y)) {
maxXOR = Math.Max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
public static void Main() {
int[] nums = { 1, 2, 3, 4, 5 };
Console.WriteLine(MaxStrongPairXOR(nums));
}
}The Python implementation loops through all possible pairs and checks if they satisfy the problem's condition. If they do, it computes the XOR and keeps track of the maximum.
Time Complexity: O(n^2)
Space Complexity: O(1)
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.
def maxStrongPairXOR(nums):
nums.sort()
max_xor = float('-inf')
for i in range(len(nums)):
for j in range(i, len(nums)):
x, y = nums[i], nums[j]
if abs(x - y) <= x:
max_xor = max(max_xor, x ^ y)
return max_xor
nums = [1, 2, 3, 4, 5]
print(maxStrongPairXOR(nums))import java.util.Arrays;
public class StrongPairXOR {
public static int maxStrongPairXOR(int[] nums) {
Arrays.sort(nums);
int maxXOR = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int x = nums[i];
int y = nums[j];
if (Math.abs(x - y) <= x) {
maxXOR = Math.max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
System.out.println(maxStrongPairXOR(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int maxStrongPairXOR(vector<int>& nums) {
sort(nums.begin(), nums.end());
int maxXOR = INT_MIN;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i; j < nums.size(); ++j) {
int x = nums[i];
int y = nums[j];
if (abs(x - y) <= x) {
maxXOR = max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
cout << maxStrongPairXOR(nums) << endl;
return 0;
}function maxStrongPairXOR(nums) {
nums.sort((a, b) => a - b);
let maxXOR = -Infinity;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
let x = nums[i], y = nums[j];
if (Math.abs(x - y) <= x) {
maxXOR = Math.max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
let nums = [1, 2, 3, 4, 5];
console.log(maxStrongPairXOR(nums));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int maxStrongPairXOR(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int maxXOR = INT_MIN;
for (int i = 0; i < numsSize; ++i) {
for (int j = i; j < numsSize; ++j) {
int x = nums[i];
int y = nums[j];
if (abs(x - y) <= x) {
int xorValue = x ^ y;
if (xorValue > maxXOR) {
maxXOR = xorValue;
}
}
}
}
return maxXOR;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxStrongPairXOR(nums, size));
return 0;
}using System;
public class StrongPairXOR {
public static int MaxStrongPairXOR(int[] nums) {
Array.Sort(nums);
int maxXOR = int.MinValue;
for (int i = 0; i < nums.Length; i++) {
for (int j = i; j < nums.Length; j++) {
int x = nums[i];
int y = nums[j];
if (Math.Abs(x - y) <= x) {
maxXOR = Math.Max(maxXOR, x ^ y);
}
}
}
return maxXOR;
}
public static void Main() {
int[] nums = { 1, 2, 3, 4, 5 };
Console.WriteLine(MaxStrongPairXOR(nums));
}
}Utilizing Python's efficient sorting before evaluating possible pairs helps the code manage operations more consistently and quickly.
Time Complexity: O(n^2)
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).
function maximumStrongPairXor(nums: number[]): number {
let ans = 0;
for (const x of nums) {
for (const y of nums) {
if (Math.abs(x - y) <= Math.min(x, y)) {
ans = Math.max(ans, x ^ y);
}
}
}
return ans;
}func maximumStrongPairXor(nums []int) (ans int) {
for _, x := range nums {
for _, y := range nums {
if abs(x-y) <= min(x, y) {
ans = max(ans, x^y)
}
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}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.
class Trie {
children: (Trie | null)[];
cnt: number;
constructor() {
this.children = [null, null];
this.cnt = 0;
}
insert(x: number): void {
let node: Trie | null = this;
for (let i = 7; i >= 0; i--) {
const v = (x >> i) & 1;
if (node.children[v] === null) {
node.children[v] = new Trie();
}
node = node.children[v] as Trie;
node.cnt++;
}
}
search(x: number): number {
let node: Trie | null = this;
let ans = 0;
for (let i = 7; i >= 0; i--) {
const v = (x >> i) & 1;
if (node.children[v ^ 1] !== null && (node.children[v ^ 1] as Trie).cnt > 0) {
ans |= 1 << i;
node = node.children[v ^ 1] as Trie;
} else {
node = node.children[v] as Trie;
}
}
return ans;
}
remove(x: number): void {
let node: Trie | null = this;
for (let i = 7; i >= 0; i--) {
const v = (x >> i) & 1;
node = node.children[v] as Trie;
node.cnt--;
}
}
}
function maximumStrongPairXor(nums: number[]): number {
nums.sort((a, b) => a - b);
const tree = new Trie();
let ans = 0;
let i = 0;
for (const y of nums) {
tree.insert(y);
while (y > nums[i] * 2) {
tree.remove(nums[i++]);
}
ans = Math.max(ans, tree.search(y));
}
return ans;
}type Trie struct {
children [2]*Trie
cnt int
}
func newTrie() *Trie {
return &Trie{}
}
func (t *Trie) insert(x int) {
node := t
for i := 7; i >= 0; i-- {
v := (x >> uint(i)) & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
node.cnt++
}
}
func (t *Trie) search(x int) int {
node := t
ans := 0
for i := 7; i >= 0; i-- {
v := (x >> uint(i)) & 1
if node.children[v^1] != nil && node.children[v^1].cnt > 0 {
ans |= 1 << uint(i)
node = node.children[v^1]
} else {
node = node.children[v]
}
}
return ans
}
func (t *Trie) remove(x int) {
node := t
for i := 7; i >= 0; i-- {
v := (x >> uint(i)) & 1
node = node.children[v]
node.cnt--
}
}
func maximumStrongPairXor(nums []int) (ans int) {
sort.Ints(nums)
tree := newTrie()
i := 0
for _, y := range nums {
tree.insert(y)
for ; y > nums[i]*2; i++ {
tree.remove(nums[i])
}
ans = max(ans, tree.search(y))
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with All Pair Checking | Time Complexity: O(n^2) |
| Approach 2: Optimized Search with Sorted Array | Time Complexity: O(n^2) |
| Enumeration | – |
| Sorting + Binary Trie | – |
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 |
Frequently asked questions
Is Maximum Strong Pair XOR I easy or hard?
Maximum Strong Pair XOR I is classified as an Easy problem. The core challenge is understanding the strong pair condition and applying a simple nested loop with XOR calculation. No advanced data structures are required.
Maximum Strong Pair XOR I Python/Java solution
Implement two nested loops that check whether each pair satisfies |nums[i] − nums[j]| ≤ min(nums[i], nums[j]). If valid, compute nums[i] ^ nums[j] and track the maximum value. The same logic works in Python, Java, C++, C#, and JavaScript with O(n²) time complexity.
How to solve Maximum Strong Pair XOR I in O(n)?
An O(n) solution is generally not achievable for this specific version due to the need to evaluate pair relationships. The straightforward and accepted approach is O(n²). More advanced techniques such as Trie-based bit optimization appear in the harder variant of the problem, but they are unnecessary for this version.
What is the best approach for Maximum Strong Pair XOR I?
The practical approach is checking all pairs while validating the strong pair condition |x − y| ≤ min(x, y). This brute force strategy runs in O(n²) time and O(1) space and works well because the problem has small input constraints. A sorted-array optimization can reduce unnecessary comparisons but the overall complexity remains quadratic.
Is Maximum Strong Pair XOR I asked at Google/Amazon/Meta?
Array and XOR-based pair problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving bit manipulation or maximum XOR calculations are especially common because they test understanding of bitwise operations and pair constraints.
What data structure is used in Maximum Strong Pair XOR I?
The basic solution relies on simple array traversal and bitwise XOR operations. Some optimized discussions reference sorting, sliding window techniques, or a Trie for maximum XOR problems, though a Trie is not required for the easy version.
What is the time complexity of Maximum Strong Pair XOR I?
The typical solution runs in O(n²) time because every pair may need to be evaluated to verify the strong pair condition and compute XOR. Space complexity is O(1) since only a few variables are used to track the maximum XOR value.