What is the brute force approach and complexity for Maximum XOR of Two Numbers in an Array?

XOR every pair of numbers and keep the largest; O(n²) with time complexity O(n²) and space complexity O(1).

What is the optimal approach and complexity for Maximum XOR of Two Numbers in an Array?

Insert every number bit by bit, highest first; for each number, walk toward the opposite bit with optimal time complexity O(31 · n) and space complexity O(31 · n).

How do you identify the pattern for Maximum XOR of Two Numbers in an Array?

Look for key signals in the prompt: "largest XOR of two numbers" indicates XOR is decided bit by bit, and the top bit counts most → build the structure over bits, highest first.; "any pair from the list" indicates We need each number's best partner without checking all of them → a trie we can walk toward the opposite bit.; "values up to 2^31 − 1" indicates A fixed width of 31 bits → a trie of fixed depth 31, so each walk costs 31 steps..

Maximum XOR of Two Numbers in an Array

Medium·LeetCode #421Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBitwise trie (greedy: opposite bit first)

Complexity:O(n²)→O(31 · n)

Key Insight

Put every number into a binary trie from the highest bit down. Each node is one bit, 0 or 1. For each number x, walk the trie from the top bit and prefer the opposite bit, because that puts a 1 into the XOR. If the opposite child is missing, take the same child. The walk gives the largest XOR that x can make with any number. The best over all x is the answer.

Core Validity Invariant

The walk always stays on a path that exists in the trie, so the partner it builds is a real number from the list. At each bit it takes the opposite child whenever one exists, because that is the best choice for that bit.

Problem

You get a list of non-negative integers nums. Pick two positions in the list (they may be the same position) and XOR the two numbers. Return the largest XOR you can get.

XOR compares two numbers bit by bit. A bit of the result is 1 only when the two bits in that place are different. The same position twice gives 0, which never beats a pair of different numbers.

Input

nums: a list of non-negative integers.

Output

One integer: the largest value of nums[i] XOR nums[j].

Example 1

Input: nums = [3, 10, 5, 25, 2, 8]

Output: 28

5 XOR 25 = 28, which is the largest. The two largest numbers, 25 and 10, only give 25 XOR 10 = 19.

Example 2

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

Output: 127

91 XOR 36 = 127, which is 1111111 in binary: seven ones in a row.

Constraints

• 1 ≤ nums.length ≤ 2 · 10^5
• 0 ≤ nums[i] ≤ 2^31 − 1

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
XOR gives a 1 only where the two bits differ. Which bit of the answer matters most?
2.
If I could pick any two numbers, which bit would I want to be 1 first? Would the lower bits ever be worth more?
3.
How many pairs are there if the list has 2 · 10^5 numbers?
4.
Suppose I already know one number x. Could I find its best partner from its bits, without looking at every other number?
5.
A number up to 2^31 − 1 has how many bits? In what order should I look at them?

Brute force approach

Idea

The answer is the XOR of some pair, so compute the XOR of every pair of positions and keep the largest. This needs no clever idea, but it checks about n²/2 pairs.

Thinking process

1
The answer must come from some pair, so trying every pair must find it.
2
Example: nums = [3, 10, 5, 25, 2, 8] has 15 pairs. Take 25: 3 XOR 25 = 26, 10 XOR 25 = 19, 5 XOR 25 = 28, 2 XOR 25 = 27, 8 XOR 25 = 17.
3
Keep a running best while looping. Across all 15 pairs the largest is 5 XOR 25 = 28, and that is the answer.
4
Looking only at pairs with i < j is enough: x XOR x is 0, and the best starts at 0.

Code & Implementation

brute.cpp

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int best = 0;   // a single number gives 0, and XOR never goes below 0
        // Every pair of different positions. x XOR x is 0, so i < j is enough.
        for (size_t i = 0; i < nums.size(); i++)
            for (size_t j = i + 1; j < nums.size(); j++)
                best = max(best, nums[i] ^ nums[j]);
        return best;
    }
};

class Solution {
    public int findMaximumXOR(int[] nums) {
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                best = Math.max(best, nums[i] ^ nums[j]);
            }
        }
        return best;
    }
}

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        best = 0
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                best = max(best, nums[i] ^ nums[j])
        return best

export function findMaximumXOR(nums: number[], ...args: any[]): number {
    let best = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const val = nums[i] ^ nums[j];
            if (val > best) best = val;
        }
    }
    return best;
}

Complexity

Time O(n²)Space O(1)

For n = 2 · 10^5 there are about 2 · 10^10 pairs, far too many. We need a way to find each number's best partner directly.

Optimized approach

Idea

Start from brute force

The brute force tries every pair. For one number x, it compares x with every other number, even though the bits of x already say what a good partner looks like.

Find the repeated work

Every pair is XORed from scratch, and the search for one x teaches nothing about the next x. Most pairs are weak: they agree on the top bits, so the answer gets a 0 where a 1 was possible.

Define the state — what variables do I need?

trie: Every number's bits from bit 30 down to bit 0. A node is a bit prefix, and its two children are the next bit being 0 or 1.
x: The number being matched right now.
value: The XOR of `x` and the partner the walk is building, one bit at a time from the top.
best: The largest value seen for any `x`. At the end, this is the answer.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Insert: for each bit from 30 down to 0

Create the child for this bit if it is missing, then move down.

Numbers that share their top bits share the same nodes, so the trie stays compact.

Query x: the opposite child exists

`value |= 1 << b`, then move to the opposite child.

This bit of the XOR is 1. Lower bits can never add up to 2^b, so this is the right move.

Query x: the opposite child is missing

Move to the same-bit child. This bit of `value` stays `0`.

No number has the opposite bit here, so this bit of the XOR is 0. The same-bit child exists, because x was inserted.

End of the walk

`best = max(best, value)`.

value is the XOR of x with a real number from the list.

What does the current window add to the answer?

After x's walk, value is the largest XOR that x makes with any number in the list. The largest over all x is the largest XOR of any pair.

Code & Implementation

optimal.cpp

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        // Values are between 0 and 2^31 - 1, so every number has 31 bits: bit 30 down to bit 0.
        const int BITS = 31;

        // Binary trie, high bit first. kids[node][bit] = index of the child for that bit (0 = none).
        // Node 0 is the root, so 0 can safely mean "no child".
        vector<array<int, 2>> kids(1);

        for (int x : nums) {
            int node = 0;
            for (int b = BITS - 1; b >= 0; b--) {
                int bit = (x >> b) & 1;
                if (kids[node][bit] == 0) {
                    int fresh = (int)kids.size();
                    kids.push_back({0, 0});
                    kids[node][bit] = fresh;
                }
                node = kids[node][bit];
            }
        }

        int best = 0;
        for (int x : nums) {
            // Walk x's bits from the top. Prefer the opposite bit: it puts a 1 into the XOR.
            int node = 0, value = 0;   // value = the XOR built so far
            for (int b = BITS - 1; b >= 0; b--) {
                int want = 1 - ((x >> b) & 1);
                if (kids[node][want] != 0) {
                    value |= 1 << b;
                    node = kids[node][want];
                } else {
                    // No number has the opposite bit here, so this bit of the XOR is 0.
                    // x itself was inserted, so the same-bit child exists.
                    node = kids[node][1 - want];
                }
            }
            best = max(best, value);
        }
        return best;
    }
};

class Solution {
    static class TrieNode {
        TrieNode[] child = new TrieNode[2];
    }

    public int findMaximumXOR(int[] nums) {
        final int BITS = 31;
        TrieNode root = new TrieNode();

        for (int x : nums) {
            TrieNode cur = root;
            for (int b = BITS - 1; b >= 0; b--) {
                int bit = (x >> b) & 1;
                if (cur.child[bit] == null) {
                    cur.child[bit] = new TrieNode();
                }
                cur = cur.child[bit];
            }
        }

        int best = 0;
        for (int x : nums) {
            TrieNode cur = root;
            int value = 0;
            for (int b = BITS - 1; b >= 0; b--) {
                int bit = (x >> b) & 1;
                int want = 1 - bit;
                if (cur.child[want] != null) {
                    value |= (1 << b);
                    cur = cur.child[want];
                } else {
                    cur = cur.child[bit];
                }
            }
            best = Math.max(best, value);
        }
        return best;
    }
}

class TrieNode:
    def __init__(self):
        self.child: list[TrieNode | None] = [None, None]

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        BITS = 31
        root = TrieNode()

        for x in nums:
            cur = root
            for b in range(BITS - 1, -1, -1):
                bit = (x >> b) & 1
                if not cur.child[bit]:
                    cur.child[bit] = TrieNode()
                cur = cur.child[bit]

        best = 0
        for x in nums:
            cur = root
            value = 0
            for b in range(BITS - 1, -1, -1):
                bit = (x >> b) & 1
                want = 1 - bit
                if cur.child[want]:
                    value |= (1 << b)
                    cur = cur.child[want]
                else:
                    cur = cur.child[bit]
            best = max(best, value)
        return best

class TrieNode {
    child: (TrieNode | null)[] = [null, null];
}

export function findMaximumXOR(nums: number[], ...args: any[]): number {
    const BITS = 31;
    const root = new TrieNode();

    for (const x of nums) {
        let cur = root;
        for (let b = BITS - 1; b >= 0; b--) {
            const bit = (x >> b) & 1;
            if (!cur.child[bit]) cur.child[bit] = new TrieNode();
            cur = cur.child[bit]!;
        }
    }

    let best = 0;
    for (const x of nums) {
        let cur = root;
        let value = 0;
        for (let b = BITS - 1; b >= 0; b--) {
            const bit = (x >> b) & 1;
            const want = 1 - bit;
            if (cur.child[want]) {
                value |= (1 << b);
                cur = cur.child[want]!;
            } else {
                cur = cur.child[bit]!;
            }
        }
        if (value > best) best = value;
    }
    return best;
}

Complexity

Time O(31 · n)Space O(31 · n)

The brute force checks about n²/2 pairs. The trie checks each number's best partner in 31 steps, so the work is about 31 · n. The cost is memory: each number can add up to 31 new nodes, so this is the price of the speed. Each number is inserted and walked once, 31 bits each. The trie has at most 31 nodes per number, about 6 million at the largest input.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	XOR every pair of numbers and keep the largest; O(n²)	O(n²)	O(1)
Optimal	Insert every number bit by bit, highest first; for each number, walk toward the opposite bit	O(31 · n)	O(31 · n)

Why does this belong to this pattern?

Clues in the problem statement

“largest XOR of two numbers”XOR is decided bit by bit, and the top bit counts most → build the structure over bits, highest first.
“any pair from the list”We need each number's best partner without checking all of them → a trie we can walk toward the opposite bit.
“values up to 2^31 − 1”A fixed width of 31 bits → a trie of fixed depth 31, so each walk costs 31 steps.

store numbers bit by bit, high → low+for each x, take the opposite bit when it exists+a higher bit outweighs all lower bits together→Bitwise trie (greedy: opposite bit first)

This is the trie idea with bits instead of letters: each node is a 0 or a 1, and the depth is fixed at 31. The new rule is greedy: take the opposite bit whenever it exists, because 2^b is bigger than all the lower bits added together (2^b − 1 at most). Implement Trie walks the letters of one word. Here the walk follows x's bits and looks for its best partner. Maximum XOR With an Element From Array uses the same walk, with a limit on which numbers may be used.

Don't make this mistake

Walking the bits from the low end up

✗ for (int b = 0; b < BITS; b++) { int want = 1 - ((x >> b) & 1); ... // the trie's first level is bit 0

✓ for (int b = BITS - 1; b >= 0; b--) { int want = 1 - ((x >> b) & 1); ... // highest bit first

The highest bit is worth more than all the lower bits together, so its decision has to come first. Walking from bit 0 up decides the low bits first and locks in the high bits later. In the dry run, [3, 10, 5, 25, 2, 8] built and walked this way gives 27, not 28.

XOR of the two largest numbers (pattern confusion)

✗ sort(nums.begin(), nums.end()); return nums.back() ^ nums[nums.size() - 2];

✓ int best = 0; for (int x : nums) best = max(best, walk(x)); // walk = the greedy trie walk

Big numbers do not make a big XOR; the bit pattern does. In the dry run, the two largest are 25 and 10, and 25 XOR 10 = 19. But 5 XOR 25 = 28, and 5 is one of the small numbers. Each number needs its own best partner.

Following the opposite child without checking it exists

✗ node = kids[node][want]; // always take the opposite child

✓ if (kids[node][want] != 0) { value |= 1 << b; node = kids[node][want]; } else { node = kids[node][1 - want]; // same child }

When no number has the opposite bit, the child index is 0, which is the root. The walk then jumps back to the top and reads the wrong bits. With the dry run's 5-bit trie, this version reports 29 (for 5 and 25), but the true answer is 28.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Trie translate into production architectures and low-level memory mechanics.

LLD Practice

Autocomplete & Search Engine

Prefix query caching, ranking, and memory-efficient trie compaction.

Explore Track

C++ Internals

Memory Alignment & Struct Padding

Minimizing pointer overhead and cache misses across 26-ary trie nodes.

Explore Track

Maximum XOR With an Element From Array