Maximum XOR of Two Numbers in an Array solution and explanation
Google
9 more videos on this problem
maximum xor of two numbers in an array leetcode | leetcode 421 | bitwise solutionNaresh Gupta · 13:37 · 26K views
Max XOR of 2 numbers in an array | Leetcode #421Techdose · 20:23 · 7K views
Leetcode 421 | Maximum XOR of Two Numbers in an Array | BitWise | XOR | Trie TreeHellgeek Arena · 10:17 · 7K views
Maximum XOR of Two Numbers in an Array | Leet code 421 | Theory explained + Python codeSai Anish Malla · 24:11 · 6K views
421. Maximum XOR of Two Numbers in an Array (Leetcode Problem)viralSongs · 11:20 · 5K views
LeetCode 421. Maximum XOR of Two Numbers in an ArraycoderZ · 11:16 · 2K views
Maximum XOR of Two Numbers in an Array | LeetCode 421 | September LeetCode Challenge | Day 16Learn Code Repeat · 17:27 · 2K views
Daily Leetcode #169: Sep 16, 2020 - 421. Maximum XOR of Two Numbers in an ArrayProgramming Live with Larry · 16:21 · 2K views
Maximum XOR of Two Numbers in an Array | HashMap | Trie | Maths | Bits | 421 LeetCode | DAY 27CodeWithSunny · 23:36 · 1K views
Leetcode 421. Maximum XOR of Two Numbers in an Array | Trie ProblemINFO DECODER · 17:53 · 426 views
The problem
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Example 1:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 231 - 1
Approach overview
Problem Overview: Given an integer array nums, you need to find two numbers whose XOR value is the largest possible. The challenge is identifying the pair that maximizes the XOR operation without checking every combination when the array becomes large.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
The most direct strategy checks every possible pair in the array. Iterate through the array using two nested loops and compute nums[i] ^ nums[j] for each pair. Track the maximum value seen so far and return it after scanning all combinations. This method uses basic array traversal and bit manipulation operations.
The logic is easy to implement and useful for validating correctness on small datasets. However, the time complexity grows quickly because every element is compared with every other element. With n numbers, the algorithm performs roughly n*(n-1)/2 XOR operations, making it impractical for large inputs.
Approach 2: Trie-Based Bit Optimization (O(n * W) time, O(n * W) space)
A more efficient solution builds a binary Trie based on the bit representation of each number. Each level of the Trie represents a bit position (usually 31 down to 0 for 32‑bit integers). While inserting numbers, you store paths for 0 and 1 bits. To maximize XOR, traverse the Trie preferring the opposite bit at each level because XOR becomes 1 when bits differ.
For every number in the array, walk the Trie from the most significant bit to the least significant bit. If the current bit is 0, try moving to the 1 branch; if the bit is 1, try moving to the 0 branch. This greedy decision maximizes the resulting XOR value bit by bit. Each insertion and query touches at most W bits, where W is the integer bit length (typically 32).
The Trie structure allows you to efficiently search for the best complementary number already inserted. Instead of comparing against all elements, you narrow the search using bit decisions. The result is near-linear performance relative to the input size.
Recommended for interviews: Interviewers expect the Trie-based approach because it demonstrates strong understanding of bitwise operations and optimized search structures. Starting with the brute force approach shows you understand the problem baseline. Transitioning to the Trie solution shows algorithmic maturity and familiarity with advanced bitwise greedy strategies used in many XOR-related problems.
Approach 1: Brute Force Approach
This approach involves iterating over all possible pairs of numbers in the array and calculating their XOR. We keep track of the maximum XOR value encountered during these iterations.
Though straightforward, this method is not efficient for large arrays, as it involves checking each pair of numbers.
def findMaximumXOR(nums):
max_xor = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
max_xor = max(max_xor, nums[i] ^ nums[j])
return max_xor
nums = [3, 10, 5, 25, 2, 8]
print("Maximum XOR:", findMaximumXOR(nums))public class Solution {
public int findMaximumXOR(int[] nums) {
int maxXor = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int xorValue = nums[i] ^ nums[j];
if (xorValue > maxXor) {
maxXor = xorValue;
}
}
}
return maxXor;
}
public static void main(String[] args) {
int[] nums = {3, 10, 5, 25, 2, 8};
Solution solution = new Solution();
System.out.println("Maximum XOR: " + solution.findMaximumXOR(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int findMaximumXOR(vector<int>& nums) {
int maxXor = 0;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i; j < nums.size(); ++j) {
int xorValue = nums[i] ^ nums[j];
maxXor = max(maxXor, xorValue);
}
}
return maxXor;
}
int main() {
vector<int> nums = {3, 10, 5, 25, 2, 8};
cout << "Maximum XOR: " << findMaximumXOR(nums) << endl;
return 0;
}function findMaximumXOR(nums) {
let maxXor = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
maxXor = Math.max(maxXor, nums[i] ^ nums[j]);
}
}
return maxXor;
}
const nums = [3, 10, 5, 25, 2, 8];
console.log("Maximum XOR:", findMaximumXOR(nums));#include <stdio.h>
int findMaximumXOR(int* nums, int numsSize) {
int maxXor = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i; j < numsSize; j++) {
int xorValue = nums[i] ^ nums[j];
if (xorValue > maxXor) {
maxXor = xorValue;
}
}
}
return maxXor;
}
int main() {
int nums[] = {3, 10, 5, 25, 2, 8};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Maximum XOR: %d\n", findMaximumXOR(nums, numsSize));
return 0;
}using System;
class Solution {
public int FindMaximumXOR(int[] nums) {
int maxXor = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i; j < nums.Length; j++) {
maxXor = Math.Max(maxXor, nums[i] ^ nums[j]);
}
}
return maxXor;
}
static void Main() {
int[] nums = {3, 10, 5, 25, 2, 8};
Solution sol = new Solution();
Console.WriteLine("Maximum XOR: " + sol.FindMaximumXOR(nums));
}
}The Python function findMaximumXOR iterates through every pair of integers in the list nums using two nested loops. For each pair, it computes the XOR and updates the maximum value found.
Time Complexity: O(n^2), as every pair in the list is considered.
Space Complexity: O(1), using constant space.
Approach 2: Trie-Based Approach
This approach makes use of a Trie data structure to efficiently maximize the XOR computation. By examining the binary representation of numbers, we can leverage the Trie to only explore branches that potentially maximize the XOR result.
The Trie helps in finding complementary patterns (bits) efficiently by using bit manipulation and path traversal.
class TrieNode:
def __init__(self):
self.children = {}
class Solution:
def findMaximumXOR(self, nums):
root = TrieNode()
maxXor, mask = 0, 0
for num in nums:
node, xorNode = root, root
currentXor = 0
for i in range(31, -1, -1):
bit = (num >> i) & 1
if bit not in node.children:
node.children[bit] = TrieNode()
node = node.children[bit]
toggledBit = 1 - bit
if toggledBit in xorNode.children:
currentXor = currentXor | (1 << i)
xorNode = xorNode.children[toggledBit]
else:
xorNode = xorNode.children.get(bit, xorNode)
maxXor = max(maxXor, currentXor)
self.insert(root, num)
return maxXor
def insert(self, root, num):
node = root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if bit not in node.children:
node.children[bit] = TrieNode()
node = node.children[bit]
# Example Test
nums = [3, 10, 5, 25, 2, 8]
sol = Solution()
print("Maximum XOR:", sol.findMaximumXOR(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 = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
public int findMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
int maxXor = 0;
for (int num : nums) {
TrieNode node = root;
int curXor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[1 - bit] != null) {
curXor |= (1 << i);
node = node.children[1 - bit];
} else {
node = node.children[bit];
}
}
maxXor = Math.max(maxXor, curXor);
insert(root, num);
}
return maxXor;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {3, 10, 5, 25, 2, 8};
System.out.println("Maximum XOR: " + solution.findMaximumXOR(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
class TrieNode {
public:
TrieNode* children[2];
TrieNode() { children[0] = children[1] = NULL; }
};
void insert(TrieNode* root, int num) {
TrieNode* node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = new TrieNode();
}
node = node->children[bit];
}
}
int findMaximumXOR(vector<int>& nums) {
TrieNode* root = new TrieNode();
int maxXor = 0;
for (int num : nums) {
TrieNode* node = root;
int currXor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node->children[1 - bit]) {
currXor |= (1 << i);
node = node->children[1 - bit];
} else {
node = node->children[bit];
}
}
maxXor = max(maxXor, currXor);
insert(root, num);
}
return maxXor;
}
int main() {
vector<int> nums = {3, 10, 5, 25, 2, 8};
cout << "Maximum XOR: " << findMaximumXOR(nums) << endl;
return 0;
}class TrieNode {
constructor() {
this.children = {};
}
}
function findMaximumXOR(nums) {
let root = new TrieNode();
let maxXor = 0;
for (let num of nums) {
let node = root, xorNode = root;
let currentXor = 0;
for (let i = 31; i >= 0; i--) {
let bit = (num >> i) & 1;
if (!(bit in node.children)) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
let toggledBit = 1 - bit;
if (toggledBit in xorNode.children) {
currentXor |= (1 << i);
xorNode = xorNode.children[toggledBit];
} else {
xorNode = xorNode.children[bit];
}
}
maxXor = Math.max(maxXor, currentXor);
insert(root, num);
}
return maxXor;
}
function insert(root, num) {
let node = root;
for (let i = 31; i >= 0; i--) {
let bit = (num >> i) & 1;
if (!(bit in node.children)) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
// Example Test
let nums = [3, 10, 5, 25, 2, 8];
console.log("Maximum XOR:", findMaximumXOR(nums));#include <stdio.h>
#include <stdlib.h>
#define MAX_BITS 31
typedef struct TrieNode {
struct TrieNode* children[2];
} TrieNode;
TrieNode* createNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->children[0] = node->children[1] = NULL;
return node;
}
void insert(TrieNode* root, int num) {
TrieNode* node = root;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = createNode();
}
node = node->children[bit];
}
}
int findMaximumXOR(int* nums, int numsSize) {
TrieNode* root = createNode();
int maxXor = 0;
for (int i = 0; i < numsSize; i++) {
TrieNode* node = root;
int currXor = 0;
for (int j = MAX_BITS; j >= 0; j--) {
int bit = (nums[i] >> j) & 1;
// Choose opposite bit if available for maximizing XOR
if (node->children[1 - bit]) {
currXor |= (1 << j);
node = node->children[1 - bit];
} else {
node = node->children[bit];
}
}
maxXor = currXor > maxXor ? currXor : maxXor;
insert(root, nums[i]);
}
return maxXor;
}
int main() {
int nums[] = {3, 10, 5, 25, 2, 8};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Maximum XOR: %d\n", findMaximumXOR(nums, numsSize));
return 0;
}using System;
class TrieNode {
public TrieNode[] children = new TrieNode[2];
}
public class Solution {
private void Insert(TrieNode root, int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
public int FindMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
int maxXor = 0;
foreach (int num in nums) {
TrieNode node = root;
TrieNode xorNode = root;
int currentXor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
int toggledBit = 1 - bit;
if (xorNode.children[toggledBit] != null) {
currentXor |= (1 << i);
xorNode = xorNode.children[toggledBit];
} else {
xorNode = xorNode.children[bit];
}
}
maxXor = Math.Max(maxXor, currentXor);
Insert(root, num);
}
return maxXor;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {3, 10, 5, 25, 2, 8};
Console.WriteLine("Maximum XOR: " + solution.FindMaximumXOR(nums));
}
}This Python solution adds numbers into a Trie and attempts to maximize the XOR result by exploring complementary bit paths during insertion and traversal.
Time Complexity: O(n * W), with W being the bit length.
Space Complexity: O(n * W), corresponding to the Trie structure's storage needs.
Approach 3: Default Approach
type Trie struct {
children [2]*Trie
}
func newTrie() *Trie {
return &Trie{}
}
func (t *Trie) insert(x int) {
node := t
for i := 30; i >= 0; i-- {
v := x >> i & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}
func (t *Trie) search(x int) int {
node := t
ans := 0
for i := 30; i >= 0; i-- {
v := x >> i & 1
if node.children[v^1] != nil {
ans |= 1 << i
node = node.children[v^1]
} else {
node = node.children[v]
}
}
return ans
}
func findMaximumXOR(nums []int) (ans int) {
trie := newTrie()
for _, x := range nums {
trie.insert(x)
ans = max(ans, trie.search(x))
}
return ans
}struct Trie {
children: [Option<Box<Trie>>; 2],
}
impl Trie {
fn new() -> Trie {
Trie {
children: [None, None],
}
}
fn insert(&mut self, x: i32) {
let mut node = self;
for i in (0..=30).rev() {
let v = ((x >> i) & 1) as usize;
if node.children[v].is_none() {
node.children[v] = Some(Box::new(Trie::new()));
}
node = node.children[v].as_mut().unwrap();
}
}
fn search(&self, x: i32) -> i32 {
let mut node = self;
let mut ans = 0;
for i in (0..=30).rev() {
let v = ((x >> i) & 1) as usize;
if let Some(child) = &node.children[v ^ 1] {
ans |= 1 << i;
node = child.as_ref();
} else {
node = node.children[v].as_ref().unwrap();
}
}
ans
}
}
impl Solution {
pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
let mut trie = Trie::new();
let mut ans = 0;
for &x in nums.iter() {
trie.insert(x);
ans = ans.max(trie.search(x));
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), as every pair in the list is considered. |
| Trie-Based Approach | Time Complexity: O(n * W), with W being the bit length. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small arrays or quick baseline solution to verify correctness |
| Trie-Based Bit Optimization | O(n * W) ≈ O(n) | O(n * W) | Large arrays where near-linear performance is required |
Frequently asked questions
Is Maximum XOR of Two Numbers in an Array easy or hard?
Maximum XOR of Two Numbers in an Array is generally classified as a medium difficulty problem. The brute force idea is straightforward, but identifying the Trie-based optimization requires understanding of bit manipulation and prefix tree structures.
How to solve Maximum XOR of Two Numbers in an Array in O(n)?
Use a binary Trie to store the bit representation of numbers as you iterate through the array. For each number, traverse the Trie preferring the opposite bit at each position to maximize XOR. Since each number processes at most 32 bits, the overall complexity becomes O(n * 32), which is effectively linear.
Maximum XOR of Two Numbers in an Array Python or Java solution?
Python and Java solutions typically implement the Trie-based method. Each number is inserted bit by bit into the Trie, and another traversal searches for the best complementary bits to maximize XOR. The algorithm runs in O(n * W) time and works efficiently even for large arrays.
What is the best approach for Maximum XOR of Two Numbers in an Array?
The most efficient approach uses a binary Trie built from the bit representation of numbers. For each number, you traverse the Trie and try to match opposite bits to maximize XOR at every position. This greedy bit strategy produces the optimal result with O(n * W) time complexity, where W is the number of bits (typically 32).
Is Maximum XOR of Two Numbers in an Array asked at Google Amazon Meta?
Maximum XOR of Two Numbers in an Array appears in technical interview preparation lists for companies such as Google, Amazon, and Meta. The problem tests bit manipulation skills, greedy reasoning, and familiarity with Trie data structures for efficient bitwise search.
What data structure is used in Maximum XOR of Two Numbers in an Array?
The optimal solution uses a binary Trie (also called a prefix tree) where each node represents a bit value 0 or 1. This structure allows fast traversal to find numbers with complementary bits, which maximizes the XOR value during comparison.
What is the time complexity of Maximum XOR of Two Numbers in an Array?
The brute force solution runs in O(n²) time because it compares every pair of elements. The optimized Trie-based approach runs in O(n * W) time, where W is the bit length of integers (usually 32). This effectively behaves like O(n) for typical constraints.