#421 Maximum XOR of Two Numbers in an Array

Mediumsolve on LeetCode ↗

frequently reported atBloomberg

the problem

In plain words

Return the maximum value of nums[i] XOR nums[j] over all pairs i, j (i may equal j).

in nums = [3,10,5,25,2,8]

out 28

5 ^ 25 = 00101 ^ 11001 = 11100 = 28.

in nums = [14,70,53,83,49,91,36,80,92,51,66,70]

out 127

1 ≤ nums.length ≤ 2·10⁵
0 ≤ nums[i] ≤ 2³¹ − 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTrie (prefix tree)Bit tricks (shift, mask, lowest set bit)

XOR is 1 where bits differ, and a high bit outweighs all lower bits together. Store numbers in a binary trie (bit 30 first) and, for each number, greedily walk to the opposite bit whenever that child exists.

solutions

From brute force to optimal

Compute XOR for all pairs and keep the maximum.

Two nested loops, best = max(best, a ^ b).

timeO(n²)

n(n−1)/2 pairs — 2·10¹⁰ for n = 2·10⁵, too slow.

spaceO(1)

One running max.

javajava.util.*

1class Solution {2    public int findMaximumXOR(int[] nums) {3        int best = 0;4        for (int i = 0; i < nums.length; i++)5            for (int j = i + 1; j < nums.length; j++)6                best = Math.max(best, nums[i] ^ nums[j]);7        return best;8    }9}

Build the answer from the top bit: try to set bit b, and check with a set of prefixes whether two numbers achieve it (a ^ b = c ⇔ a ^ c = b).

For b = 30..0: mask keeps the top bits.
Put every num & mask in a set.
candidate = best | (1 << b); if some p has p ^ candidate in the set, best = candidate.

timeO(31·n)

31 rounds, each O(n) with hashing.

spaceO(n)

The prefix set.

javajava.util.*

1class Solution {2    public int findMaximumXOR(int[] nums) {3        int best = 0, mask = 0;4        for (int b = 30; b >= 0; b--) {5            mask |= 1 << b;                          // keep only the top bits6            Set<Integer> prefixes = new HashSet<>();7            for (int num : nums) prefixes.add(num & mask);8            int candidate = best | (1 << b);         // can we also turn bit b on?9            for (int p : prefixes) {10                if (prefixes.contains(p ^ candidate)) { // a ^ b = c  ⇔  a ^ c = b11                    best = candidate;12                    break;13                }14            }15        }16        return best;17    }18}

Insert each number as 31 bits; then walk from the top bit preferring the opposite bit to maximise the XOR.

For each num: insert its bits 30..0 into the trie.
Query: at bit b, want = 1 − bit; if child[want] exists, set bit b of xor and go there, else follow child[bit].
best = max(best, xor).

timeO(31·n) = O(n)

Each insert and each query walks exactly 31 levels.

spaceO(31·n)

At most 31 new nodes per number.

javajava.util.*

1class Solution {2    private static final int HIGH_BIT = 30; // nums[i] < 2^31, so bit 30 is the top bit3    private static class Node {4        Node[] child = new Node[2]; // child[0] = bit 0, child[1] = bit 15    }6 7    public int findMaximumXOR(int[] nums) {8        Node root = new Node();9        int best = 0;10        for (int num : nums) {11            insert(root, num);12            best = Math.max(best, bestPartner(root, num));13        }14        return best;15    }16 17    private void insert(Node root, int num) {18        Node cur = root;19        for (int b = HIGH_BIT; b >= 0; b--) {20            int bit = (num >> b) & 1;21            if (cur.child[bit] == null) cur.child[bit] = new Node();22            cur = cur.child[bit];23        }24    }25 26    /** Largest num ^ x over every x already stored (num itself is stored, so the answer is ≥ 0). */27    private int bestPartner(Node root, int num) {28        Node cur = root;29        int xor = 0;30        for (int b = HIGH_BIT; b >= 0; b--) {31            int bit = (num >> b) & 1;32            int want = bit ^ 1;33            if (cur.child[want] != null) {34                xor |= 1 << b;35                cur = cur.child[want];36            } else {37                cur = cur.child[bit];38            }39        }40        return xor;41    }42}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private static final int HIGH_BIT = 30; // nums[i] < 2^31, so bit 30 is the top bit3    private static class Node {4        Node[] child = new Node[2]; // child[0] = bit 0, child[1] = bit 15    }6 7    public int findMaximumXOR(int[] nums) {8        Node root = new Node();9        int best = 0;10        for (int num : nums) {11            insert(root, num);12            best = Math.max(best, bestPartner(root, num));13        }14        return best;15    }16 17    private void insert(Node root, int num) {18        Node cur = root;19        for (int b = HIGH_BIT; b >= 0; b--) {20            int bit = (num >> b) & 1;21            if (cur.child[bit] == null) cur.child[bit] = new Node();22            cur = cur.child[bit];23        }24    }25 26    /** Largest num ^ x over every x already stored (num itself is stored, so the answer is ≥ 0). */27    private int bestPartner(Node root, int num) {28        Node cur = root;29        int xor = 0;30        for (int b = HIGH_BIT; b >= 0; b--) {31            int bit = (num >> b) & 1;32            int want = bit ^ 1;33            if (cur.child[want] != null) {34                xor |= 1 << b;35                cur = cur.child[want];36            } else {37                cur = cur.child[bit];38            }39        }40        return xor;41    }42}

in the room

How to say it in the interview

talk track

Explain why greedy works: 2^b > 2^(b−1) + … + 1, so winning a higher bit can never be undone.
Insert before querying so the trie is never empty (num ^ num = 0 is a valid fallback).
Mention the set-based alternative if the interviewer dislikes building a trie.

traps

Iterating bits low → high (greedy breaks).
Starting at bit 31 with signed ints — fine for non-negative inputs, but 30 is enough here and avoids sign confusion.

what they ask next

Follow-ups

Maximum XOR With an Element From Array (LC 1707): each query has a limit m?

Sort queries by m and numbers ascending; insert numbers ≤ m before answering each query (offline processing) — still O((n + q)·31).

before you submit

Edge cases to test

One number → 0 (a number XOR itself).
All numbers equal → 0.
0 and Integer.MAX_VALUE → MAX_VALUE: every bit differs.

practise next