Log inSign up
mediumLeetCodeNot Started

Maximum XOR of Two Numbers in an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < nums.length.

You must solve it in O(N) or O(32 * N) time.

Example 1 · Example 1: Small array:

Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28. 5 in binary: 00101 25 in binary: 11001 5 ^ 25: 11100 (which is 28 in decimal). Binary Trie Structure: (root) / \ bit 0 bit 1 / \ / \ ... ... ... ...

Constraints:

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the construction and mechanics of a Binary (Bitwise) Trie.
  • Apply the greedy choice property to binary representations (higher bits dominate lower bits).
  • Optimize XOR pair queries from O(N2) down to O(32 * N).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks for maximum or minimum XOR between pairs in an array.
  • Bitwise operations where higher-order bits take strict precedence over lower-order bits.
  • Need sub-quadratic O(N) time for large arrays (N up to 2 * 105).

Algorithmic Decision Tree:

  • Use a 0/1 Binary Trie of depth 31.
  • Insert all numbers into the Trie.
  • For each number, query the Trie greedily choosing the opposite bit to maximize the XOR.

Connected Patterns:

Maximum XOR With an Element From ArrayBitwise AND of Numbers RangeSubarray XOR Queries

1. All Pairs Nested Loops

Intuition

Two nested loops comparing all N*(N-1)/2 pairs. Compute nums[i] ^ nums[j] and maintain the maximum seen.

When to apply: Tiny inputs (N <= 1000).

Algorithm

  1. Step 1: Initialize maxXor = 0.
  2. Step 2: Loop i from 0 to N-1.
  3. Step 3: Loop j from i to N-1.
  4. Step 4: Update maxXor = max(maxXor, nums[i] ^ nums[j]).
  5. Step 5: Return maxXor.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int findMaximumXOR(vector<int>& nums) {
9 int maxXor = 0;
10 int n = nums.size();
11 for (int i = 0; i < n; i++) {
12 for (int j = i; j < n; j++) {
13 maxXor = max(maxXor, nums[i] ^ nums[j]);
14 }
15 }
16 return maxXor;
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<int> nums = {3, 10, 5, 25, 2, 8};
23 cout << "Max XOR: " << sol.findMaximumXOR(nums) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N^2) — Evaluates all N*(N-1)/2 pairs in O(1) arithmetic each.
  • Space complexity: O(1) — Only scalar variables used.

Why Brute Force Doesn't Scale:

N = 2 * 105 pairs require 20 billion operations, exceeding the 1-second limit by 200x.

Binary Trie checks exactly 31 bits per number, executing 31 * 200,000 ~ 6.2 million operations in ~50ms.

2. Prefix Masking with Hash Set

Intuition

Iterate bit i from 30 down to 0. Form mask to keep highest bits. Put all masked prefixes into a set. Form candidate better = maxXor | (1 << i). If there exist two prefixes p1 ^ p2 == better <=> p1 ^ better = p2, set maxXor = better.

When to apply: Compact memory alternative avoiding Trie node allocation.

Algorithm

  1. Step 1: Initialize maxXor = 0, mask = 0.
  2. Step 2: Loop i from 30 down to 0.
  3. Step 3: mask |= (1 << i). Insert num & mask for all numbers into hash set.
  4. Step 4: candidate = maxXor | (1 << i).
  5. Step 5: Check if there is prefix such that candidate ^ prefix is also in set.
  6. Step 6: If yes, maxXor = candidate.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8 int findMaximumXOR(vector<int>& nums) {
9 int maxXor = 0, mask = 0;
10 for (int i = 30; i >= 0; i--) {
11 mask |= (1 << i);
12 unordered_set<int> prefixes;
13 for (int num : nums) {
14 prefixes.insert(num & mask);
15 }
16
17 int candidate = maxXor | (1 << i);
18 for (int p : prefixes) {
19 if (prefixes.count(candidate ^ p)) {
20 maxXor = candidate;
21 break;
22 }
23 }
24 }
25 return maxXor;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> nums = {3, 10, 5, 25, 2, 8};
32 cout << "Max XOR (mask set): " << sol.findMaximumXOR(nums) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(32 * N) — 32 iterations, each building a hash set of N elements and checking in O(1).
  • Space complexity: O(N) — Hash set holds up to N masked integers.

3. Binary Trie (Bitwise 0/1 Trie) with Greedy Matching

Intuition

Each TrieNode has children[2] representing bits 0 and 1. Insert each number from bit 30 down to 0. To query max XOR for number X: from bit 30 down to 0, extract bit = (X >> i) & 1. If curr.children[1 - bit] exists, take it and add (1 << i) to current XOR; else follow curr.children[bit]. Return max across all numbers.

When to apply: Standard production & interview optimal solution for XOR maximization problems.

Algorithm

  1. Step 1: Define TrieNode with array children[2] initialized to null.
  2. Step 2: Define insert(num): loop i from 30 down to 0. Walk or allocate curr.children[bit].
  3. Step 3: Define getMaxXor(num): loop i from 30 down to 0. bit = (num >> i) & 1. If curr.children[1 - bit] exists, maxXor |= (1 << i) and move to curr.children[1 - bit], else move to curr.children[bit].
  4. Step 4: Insert all numbers into Trie.
  5. Step 5: Query getMaxXor(num) for each number and return global maximum.

Interactive Binary Trie Trace for XOR Query

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Inspect bit 4 (value 16)
Visual state
Values and pointers at this exact step
tree
Root
(root)
bit 0
0
bit 1
1 (selected)

Node order shown; add connections to display explicit tree edges.

opp: 1: b1
Check / comparison
Opposite bit 1 exists -> Take branch 1
Decision / next transition
maxXor accumulates 16.
Why this step matters

Step 1: Inspect bit 4 (value 16). x has bit 0. Opposite bit is 1. Trie has child[1] from 25. Follow child[1]. maxXor += 16.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[2];
8 TrieNode() {
9 children[0] = nullptr;
10 children[1] = nullptr;
11 }
12};
13
14class Solution {
15 TrieNode* root;
16
17 void insert(int num) {
18 TrieNode* curr = root;
19 for (int i = 30; i >= 0; i--) {
20 int bit = (num >> i) & 1;
21 if (!curr->children[bit]) curr->children[bit] = new TrieNode();
22 curr = curr->children[bit];
23 }
24 }
25
26 int getMaxXor(int num) {
27 TrieNode* curr = root;
28 int maxVal = 0;
29 for (int i = 30; i >= 0; i--) {
30 int bit = (num >> i) & 1;
31 int oppBit = 1 - bit;
32 if (curr->children[oppBit]) {
33 maxVal |= (1 << i);
34 curr = curr->children[oppBit];
35 } else {
36 curr = curr->children[bit];
37 }
38 }
39 return maxVal;
40 }
41
42public:
43 int findMaximumXOR(vector<int>& nums) {
44 root = new TrieNode();
45 for (int num : nums) insert(num);
46
47 int maxResult = 0;
48 for (int num : nums) {
49 maxResult = max(maxResult, getMaxXor(num));
50 }
51 return maxResult;
52 }
53};
54
55int main() {
56 Solution sol;
57 vector<int> nums = {3, 10, 5, 25, 2, 8};
58 cout << "Optimal Max XOR: " << sol.findMaximumXOR(nums) << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(32 * N) — Inserting N numbers of 31 bits takes 31 * N operations. Querying N numbers takes 31 * N operations.
  • Space complexity: O(32 * N) — Allocates at most 32 nodes per number in the Binary Trie.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All Pairs ComparisonO(N^2)O(1)Compare every pair (nums[i], nums[j]) with nested loops and calculate nums[i] ^ nums[j]. Track max.Quadratic pair generation.
2.Better — Bit-by-Bit Prefix Hash Set (Bitmask Greedy)O(32 * N)O(N)Iterate from bit 30 down to 0. Mask prefixes of all numbers in a hash set. Check if target = maxResult | (1 << i) is achievable using (a ^ b = target <=> a ^ target = b).32 hash set rebuilds.
3.Optimal — Binary Trie Greedy MatchingOptimalO(32 * N)O(32 * N)Insert all numbers into a Binary Trie. For each number, greedily follow the complementary bit branch to maximize XOR.None. Classical gold standard for XOR optimization.

Common Pitfalls & Crucial Edge Cases

Starting bit loop from 31 instead of 30

In signed 32-bit integers, bit 31 is the sign bit; for non-negative inputs, bit 30 is the MSB.

Searching from bit 0 up to 30

Higher bits must be greedily selected first because 2k > sum of all 2j for j < k.

Rebuilding Trie per number

Inserting all numbers once and querying takes O(N), not O(N2).

Crucial Edge Cases to Validate:

  • Array with identical numbers ([5, 5, 5]) — Any pair XORs to 0. Correctly returns 0.
  • Single pair ([2, 4]) — Only 1 comparison: 2 ^ 4 = 6. Correctly returns 6.
  • Large integers (2^31 - 1) — 31-bit representation (indices 30 down to 0) handles non-negative numbers up to 231 - 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the greedy choice property: setting the higher bit to 1 contributes more than all lower bits combined.
  2. Highlight how Binary Trie simplifies the search: each step is an O(1) decision checking children[1 - bit].
  3. State time complexity clearly as O(31 * N) which is strictly linear O(N) since 31 is a small constant.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the greedy choice of picking the opposite bit at higher positions guarantee the maximum XOR?

2.What is the branching factor of each node in a Binary Trie?

Back to DSA Sheet