Maximum Strong Pair XOR II solution and explanation
5 more videos on this problem
Leetcode Weekly contest 371 - Hard - Maximum Strong Pair XOR IIPrakhar Agrawal · 28:12 · 1K views
2935. Maximum Strong Pair XOR II - Weekly Contest 371TechTalk · 10:27 · 1K views
2935. Maximum Strong Pair XOR II | Weekly Leetcode 371codingMohan · 47:32 · 905 views
2935. Maximum Strong Pair XOR II (Leetcode Hard)Programming Live with Larry · 35:03 · 358 views
Maximum Strong Pair XOR II || LeetCode Weekly Contest 371 || Trie Solution || Explanation in HindiCode-a-tic · 35:50 · 224 views
Leetcode 2935. Maximum Strong Pair XOR II (hash table and try each bit)LetsCode · 15:19 · 34 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 = [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 - 1
Approach overview
Problem 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 1: Sort and Two Pointer Approach
By sorting the array, the problem of finding pairs becomes simpler. The key observation is that if two numbers are close enough in value, i.e., their difference is less than or equal to their minimum value, they form a strong pair. Sorting the array ensures that once a valid strong pair is found, subsequent numbers are only larger, making them incoming candidates for a strong pair condition. By employing a two-pointer technique, we efficiently navigate through the pairs to find the maximum XOR.
def maxStrongPairXOR(nums):
nums.sort()
max_xor = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
if abs(nums[i] - nums[j]) <= nums[i]:
current_xor = nums[i] ^ nums[j]
max_xor = max(max_xor, current_xor)
else:
break
return max_xor
nums = [1, 2, 3, 4, 5]
print(maxStrongPairXOR(nums))import java.util.Arrays;
public class Solution {
public static int maxStrongPairXOR(int[] nums) {
Arrays.sort(nums);
int maxXor = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
if (Math.abs(nums[i] - nums[j]) <= nums[i]) {
int currentXor = nums[i] ^ nums[j];
maxXor = Math.max(maxXor, currentXor);
} else {
break;
}
}
}
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 <algorithm>
int maxStrongPairXOR(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int maxXor = 0;
for (size_t i = 0; i < nums.size(); i++) {
for (size_t j = i; j < nums.size(); j++) {
if (std::abs(nums[i] - nums[j]) <= nums[i]) {
int currentXor = nums[i] ^ nums[j];
maxXor = std::max(maxXor, currentXor);
} else {
break;
}
}
}
return maxXor;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
std::cout << maxStrongPairXOR(nums) << std::endl;
return 0;
}function maxStrongPairXOR(nums) {
nums.sort((a, b) => a - b);
let maxXor = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
if (Math.abs(nums[i] - nums[j]) <= nums[i]) {
let currentXor = nums[i] ^ nums[j];
maxXor = Math.max(maxXor, currentXor);
} else {
break;
}
}
}
return maxXor;
}
const nums = [1, 2, 3, 4, 5];
console.log(maxStrongPairXOR(nums));#include <stdio.h>
#include <stdlib.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 = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i; j < numsSize; j++) {
if (abs(nums[i] - nums[j]) <= nums[i]) {
int currentXor = nums[i] ^ nums[j];
if (currentXor > maxXor) {
maxXor = currentXor;
}
} else {
break;
}
}
}
return maxXor;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxStrongPairXOR(nums, numsSize));
return 0;
}using System;
public class Solution {
public static int MaxStrongPairXOR(int[] nums) {
Array.Sort(nums);
int maxXor = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i; j < nums.Length; j++) {
if (Math.Abs(nums[i] - nums[j]) <= nums[i]) {
int currentXor = nums[i] ^ nums[j];
maxXor = Math.Max(maxXor, currentXor);
} else {
break;
}
}
}
return maxXor;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5};
Console.WriteLine(MaxStrongPairXOR(nums));
}
}This Python function sorts the array and uses a pair of loops to navigate through number pairs that may satisfy the strong pair condition. If such a pair is found, it calculates the XOR and compares it to the current maximum found. The Python implementation benefits from concise syntax and high-level operations, achieving functionality with minimal code.
Time Complexity: O(n^2) due to the nested loops iterating through combinations of elements.
Space Complexity: O(1) as no substantial additional memory allocation takes place besides minor loop control.
Approach 2: Bit Manipulation Optimization Approach
This approach focuses on leveraging properties of bits to directly veer toward results that maximize XOR values. By storing numbers as nodes in a trie structure (radix tree) based on their bit patterns, it's possible to find potential maximum XOR pairs by aligning complementary bits.
class TrieNode:
def __init__(self):
self.children = {}
class Solution:
def insert(self, root, num):
node = root
for i in reversed(range(20)):
bit = (num >> i) & 1
if bit not in node.children:
node.children[bit] = TrieNode()
node = node.children[bit]
def maxXorPair(self, root, num):
node = root
max_xor = 0
for i in reversed(range(20)):
bit = (num >> i) & 1
toggle_bit = 1 - bit
if toggle_bit in node.children:
max_xor |= (1 << i)
node = node.children[toggle_bit]
else:
node = node.children[bit]
return max_xor
def maxStrongPairXOR(self, nums):
root = TrieNode()
for num in nums:
self.insert(root, num)
max_xor = 0
for num in nums:
max_xor = max(max_xor, self.maxXorPair(root, num))
return max_xor
# Testing the solution:
solution = Solution()
nums = [1, 2, 3, 4, 5]
print(solution.maxStrongPairXOR(nums))import java.util.*;
class TrieNode {
TrieNode[] children = new TrieNode[2];
}
public class Solution {
private void insert(TrieNode root, int num) {
TrieNode node = root;
for (int i = 19; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
private int maxXorPair(TrieNode root, int num) {
TrieNode node = root;
int maxXor = 0;
for (int i = 19; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[1 - bit] != null) {
maxXor |= (1 << i);
node = node.children[1 - bit];
} else {
node = node.children[bit];
}
}
return maxXor;
}
public int maxStrongPairXOR(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
insert(root, num);
}
int maxXor = 0;
for (int num : nums) {
maxXor = Math.max(maxXor, maxXorPair(root, num));
}
return maxXor;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3, 4, 5};
System.out.println(solution.maxStrongPairXOR(nums));
}
}#include <iostream>
#include <vector>
#include <memory>
struct TrieNode {
std::shared_ptr<TrieNode> children[2] = {nullptr, nullptr};
};
void insert(std::shared_ptr<TrieNode> root, int num) {
auto node = root;
for (int i = 19; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = std::make_shared<TrieNode>();
}
node = node->children[bit];
}
}
int maxXorPair(std::shared_ptr<TrieNode> root, int num) {
auto node = root;
int maxXor = 0;
for (int i = 19; i >= 0; --i) {
int bit = (num >> i) & 1;
if (node->children[1 - bit]) {
maxXor |= (1 << i);
node = node->children[1 - bit];
} else {
node = node->children[bit];
}
}
return maxXor;
}
int maxStrongPairXOR(std::vector<int>& nums) {
auto root = std::make_shared<TrieNode>();
int maxXor = 0;
for (int num : nums) {
insert(root, num);
}
for (int num : nums) {
int currentXor = maxXorPair(root, num);
maxXor = std::max(maxXor, currentXor);
}
return maxXor;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
std::cout << maxStrongPairXOR(nums) << std::endl;
return 0;
}class TrieNode {
constructor() {
this.children = new Map();
}
}
class Solution {
insert(root, num) {
let node = root;
for (let i = 19; i >= 0; i--) {
const bit = (num >> i) & 1;
if (!node.children.has(bit)) {
node.children.set(bit, new TrieNode());
}
node = node.children.get(bit);
}
}
maxXorPair(root, num) {
let node = root;
let maxXor = 0;
for (let i = 19; i >= 0; i--) {
const bit = (num >> i) & 1;
const toggleBit = 1 - bit;
if (node.children.has(toggleBit)) {
maxXor |= (1 << i);
node = node.children.get(toggleBit);
} else {
node = node.children.get(bit);
}
}
return maxXor;
}
maxStrongPairXOR(nums) {
const root = new TrieNode();
for (const num of nums) {
this.insert(root, num);
}
let maxXor = 0;
for (const num of nums) {
maxXor = Math.max(maxXor, this.maxXorPair(root, num));
}
return maxXor;
}
}
const solution = new Solution();
const nums = [1, 2, 3, 4, 5];
console.log(solution.maxStrongPairXOR(nums));#include <stdio.h>
#include <stdlib.h>
struct TrieNode {
struct TrieNode* children[2];
};
struct TrieNode* getNode() {
struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
node->children[0] = node->children[1] = NULL;
return node;
}
void insert(struct TrieNode* root, int num) {
struct TrieNode* node = root;
for (int i = 19; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = getNode();
}
node = node->children[bit];
}
}
int maxXorPair(struct TrieNode* root, int num) {
struct TrieNode* node = root;
int maxXor = 0;
for (int i = 19; i >= 0; --i) {
int bit = (num >> i) & 1;
if (node->children[1 - bit]) {
maxXor |= (1 << i);
node = node->children[1 - bit];
} else {
node = node->children[bit];
}
}
return maxXor;
}
int maxStrongPairXOR(int* nums, int numsSize) {
struct TrieNode* root = getNode();
int maxXor = 0;
for (int i = 0; i < numsSize; i++) {
insert(root, nums[i]);
}
for (int i = 0; i < numsSize; i++) {
int currentXor = maxXorPair(root, nums[i]);
if (currentXor > maxXor) {
maxXor = currentXor;
}
}
return maxXor;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxStrongPairXOR(nums, numsSize));
return 0;
}using System;
using System.Collections.Generic;
public class TrieNode {
public TrieNode[] children = new TrieNode[2];
}
public class Solution {
private void Insert(TrieNode root, int num) {
TrieNode node = root;
for (int i = 19; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
private int MaxXorPair(TrieNode root, int num) {
TrieNode node = root;
int max = 0;
for (int i = 19; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[1 - bit] != null) {
max |= (1 << i);
node = node.children[1 - bit];
} else {
node = node.children[bit];
}
}
return max;
}
public int MaxStrongPairXOR(int[] nums) {
TrieNode root = new TrieNode();
foreach (int num in nums) {
Insert(root, num);
}
int maxXor = 0;
foreach (int num in nums) {
maxXor = Math.Max(maxXor, MaxXorPair(root, num));
}
return maxXor;
}
public static void Main() {
int[] nums = { 1, 2, 3, 4, 5 };
Solution solution = new Solution();
Console.WriteLine(solution.MaxStrongPairXOR(nums));
}
}This solution uses a Python dictionary for trie nodes to store child references, focusing on binary representations. It systematically inserts and calculates XOR, pivoting around sometimes-included binary manipulation.
Time Complexity: O(n) centered around direct trie operations.
Space Complexity: O(n * bit_length) proportionate to bit operations.
Approach 3: 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. In this problem, M = 2^{20}.
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 = 20; 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 = 20; 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 = 20; 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 := 20; 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 := 20; 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 := 20; 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 |
|---|---|
| Sort and Two Pointer Approach | Time Complexity: O(n^2) due to the nested loops iterating through combinations of elements. |
| Bit Manipulation Optimization Approach | Time Complexity: O(n) centered around direct trie operations. |
| Sorting + Binary Trie | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximum Strong Pair XOR II easy or hard?
Maximum Strong Pair XOR II is classified as Hard on LeetCode. The difficulty comes from combining multiple techniques: transforming the strong pair constraint, maintaining a sliding window, and using a trie or bit manipulation to compute maximum XOR efficiently.
Maximum Strong Pair XOR II Python/Java solution
Typical implementations use sorting, two pointers, and a binary trie. Python and Java solutions both insert numbers into the trie while scanning the array and query the trie to find the best XOR partner for each element.
How to solve Maximum Strong Pair XOR II in O(n)?
A strict O(n) solution is generally not achievable because computing maximum XOR requires checking bits across values. The closest efficient solution is O(n log M) using a trie or bitwise prefix technique combined with sorting and a sliding window.
What is the best approach for Maximum Strong Pair XOR II?
The most practical approach sorts the array and uses a sliding window with a binary trie. Sorting allows the strong pair condition to be simplified to y ≤ 2x, which lets you maintain valid candidates using two pointers. The trie then finds the maximum XOR for each number in O(log M) time.
Is Maximum Strong Pair XOR II asked at Google/Amazon/Meta?
Problems combining XOR maximization with constraints such as sliding windows or tries appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests knowledge of bit manipulation, data structures, and constraint optimization.
What data structure is used in Maximum Strong Pair XOR II?
The key data structure is a binary trie (prefix tree) used to store numbers in bit form and compute maximum XOR efficiently. The algorithm also uses sorting and a sliding window to enforce the strong pair condition.
What is the time complexity of Maximum Strong Pair XOR II?
The optimal solution runs in O(n log M) time, where n is the number of elements and M is the maximum value in the array. Sorting takes O(n log n), and each insertion or query in the trie takes O(log M) due to bit traversal.