hard

Maximum XOR of Two Numbers in an Array

Find the maximum XOR value obtainable from any two numbers in an array.

1. Define the problem

Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of numsi XOR numsj, where 0 ≤ i ≤ j < n. Build the answer one bit at a time, from the highest bit down , greedily assuming each new bit can be set, then checking whether any two prefixes seen so far actually achieve it.

Constraints

  • 1 ≤ nums.length ≤ 2 × 105
  • 0 ≤ numsi ≤ 231 - 1

Example

Inputnums = [3, 10, 5, 25, 2, 8]
Output28

Explanation 5 XOR 25 = 28 is the maximum XOR of any pair in the array.

2. Know the words first

In plain terms

Bit prefix
A number's leading bits down to some position, found by masking with the bits considered so far (num & mask) — comparing prefixes lets you check bit by bit without looking at the full numbers.
3. Visualize the solution

Greedily lock in each bit from the top down

Greedily lock in each bit from the top down
Statusinit

nums = [3, 10, 5, 25, 2, 8]. Scanning from the highest relevant bit (bit 4, value 16) downward.

What happens in this step

maxXor = 0
mask   = 0

nums (8-bit binary):
   3 = 00000011
  10 = 00001010
   5 = 00000101
  25 = 00011001
   2 = 00000010
   8 = 00001000

No number here has bit 5 or higher set, so mask stays empty and every prefix is 0 until bit 4 — the scan effectively starts there.
Step 1 of 4

Steps to visualize

  1. Start with maxXor = 0 and go bit by bit from the highest bit to the lowest.
  2. Extend the mask to include the current bit, and collect every number's prefix under that mask.
  3. Tentatively assume this bit can be set in the answer: candidate = maxXor | (1 << bit).
  4. If any two collected prefixes XOR together to exactly candidate, keep it — that bit really is achievable.
  5. After the lowest bit, maxXor holds the maximum XOR of any pair.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Greedily lock in each bit from the top down
Statusinit

nums = [3, 10, 5, 25, 2, 8]. Scanning from the highest relevant bit (bit 4, value 16) downward.

What happens in this step

maxXor = 0
mask   = 0

nums (8-bit binary):
   3 = 00000011
  10 = 00001010
   5 = 00000101
  25 = 00011001
   2 = 00000010
   8 = 00001000

No number here has bit 5 or higher set, so mask stays empty and every prefix is 0 until bit 4 — the scan effectively starts there.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findMaximumXOR(nums) {
  let maxXor = 0;
  let mask = 0;

  for (let bit = 31; bit >= 0; bit--) {
    mask |= 1 << bit;
    const prefixes = new Set();
    for (const num of nums) {
      prefixes.add(num & mask);
    }

    const candidate = maxXor | (1 << bit);
    let found = false;
    for (const prefix of prefixes) {
      if (prefixes.has(candidate ^ prefix)) {
        found = true;
        break;
      }
    }

    if (found) {
      maxXor = candidate;
    }
  }

  return maxXor;
}
Time
O(32n) = O(n)
Space
O(n) for the prefix set at each bit
6. Test cases

Test cases

InputExpectedCovers
nums = [3, 10, 5, 25, 2, 8]28example from the docstring
nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]127a larger array where the maximum XOR uses every low bit
nums = [0, 0]0every value identical, so the best XOR is 0
nums = [2, 4]6smallest non-trivial input, exactly two elements
nums = [8, 10, 2]10the maximum XOR involves the smallest and largest values, not the two largest
nums = [1, 2, 3, 4, 5, 6, 7]7consecutive small integers where the max XOR comes from complementary low bits

Keep reading