Maximum XOR of Two Numbers in an Array

Maximum XOR of Two Numbers in an Array medium

Description

Given an integer array nums, return the maximum value of nums[i] XOR nums[j] over all pairs i, j.

Examples

> nums = [3, 10, 5, 25, 2, 8]
  Output: 28
  Explanation: 5 XOR 25 = 28, the maximum over all pairs.
 
> nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]
  Output: 127

Constraints

1 <= nums.length <= 2 × 10^5
0 <= nums[i] < 2^31

The size (2 × 10^5) rules out the obvious O(N²) pairwise scan — that’s 4 × 10^10 operations. We need something near-linear.

Intuition — the bitwise trie

Insert every number into a trie keyed by its bits, most-significant-first (alphabet {0, 1}, depth 31). To maximize x XOR partner, walk down for x and at each bit, greedily go to the opposite bit if that child exists — opposite bits XOR to 1, and a 1 in a higher position dominates everything below it. Each number’s best partner is found in 31 steps.

Why greedy works: securing a 1 in bit 30 contributes 2^30, which is larger than the most you could ever gain (2^30 − 1) from all lower bits combined. So you never sacrifice a high bit for low ones — settle the highest bits first.

Code

⚠️

Two ways to break this: (1) walking LSB-first — the greedy “opposite bit” rule is only valid most-significant-first, because high bits dominate. (2) Using a variable bit width — pad every number to the same fixed width (31/32 bits) so the bits line up; otherwise a small number’s bits misalign against a large one’s. Both bugs produce subtly wrong answers that pass small tests.

Analysis

Time: O(N · 31) to build + O(N · 31) to query = O(N) for fixed 32-bit integers — versus O(N²) brute force.
Space: O(N · 31) for the trie (at most 2 children per node, 32 levels).

Same skin

Bitwise trie (Variations) — the technique, explained.
Maximum XOR With an Element From Array — same trie, with offline-sorted queries and a size constraint.
Count Pairs With XOR in a Range — counting variant: store subtree sizes and count partners whose XOR falls in [low, high].
Bit Manipulation (Day 17) — the bit-level reasoning the greedy choice relies on.

Word Search II Overview