Stage 4: Advanced Techniques·Trie & Bitwise

Medium#4219 min readTrieBit ManipulationLeetCode

Maximum XOR of Two Numbers in Array

Bitwise trie

Binary trie. Insert all numbers, then for each number greedily pick opposite bits.

Published Apr 16, 2026

Problem

Given a non-empty integer array nums (each element fits in 32 bits), return the maximum possible value of nums[i] XOR nums[j] over all pairs (i, j).

The answer is a single integer — the best pair's XOR — not the pair itself.

Input

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

Output

Explanation

5 XOR 25 = 28 (binary 00101 XOR 11001 = 11100). No other pair reaches that.

Input

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

Output

127

Explanation

14 XOR 113? There's no 113. But 91 XOR 36 = 127 (binary 1011011 XOR 0100100 = 1111111).

Intuition

The brute solution — try all O(n²) pairs — is obvious and instructive but falls over at n = 2·10⁵.

The key insight: XOR is bit-independent. To maximize a ^ b we greedily want each bit set, starting from the highest. The only way a bit is set in a ^ b is if a and b disagree at that bit position.

So the optimization reduces to "for each number, find a partner that disagrees with me on as many high bits as possible". Two classic techniques answer this in O(n · 31):

Prefix set with bit-by-bit greedy — at each bit, gather the high-bit prefixes of every number into a hash set, then check whether any two prefixes XOR to our tentative best-with-this-bit-set.
Bitwise trie — store each number as a 32-level binary path; to query the best partner for x, walk the trie preferring the opposite bit at every step.

Both land at O(n · 31) time; the trie is the one that generalizes (see #1707).

Approach

Brute Force

TimeO(n²)

SpaceO(1)

Try every ordered pair once and track the maximum. Passes for n ≤ 10³, times out at 10⁵.

impl Solution {
    pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
        let mut best = 0i32;
        for i in 0..nums.len() {
            for j in (i + 1)..nums.len() {
                best = best.max(nums[i] ^ nums[j]);
            }
        }
        best
    }
}

Rust · runnable

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

TypeScript · runnable

Bit-by-Bit Greedy with HashSet

TimeO(n · 31)

SpaceO(n)

Walk the bits of the answer from bit 30 down to bit 0. At each step we already know the bits we've committed to (best); we hope to extend with a 1 at the current bit.

Build prefixes = { num >> bit : num in nums } — the set of high-bit prefixes at the current level.
Let candidate = best | (1 << bit).
If any two prefixes p, q satisfy p ^ q = candidate, we can achieve this candidate; keep it. That check is any p such that candidate ^ p in prefixes.
Otherwise, drop the bit and move on.

The cleverness is that we never materialize the pair — we only care whether one exists.

use std::collections::HashSet;

impl Solution {
    pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
        let mut best = 0i32;
        for bit in (0..31).rev() {
            let mask = !0i32 << bit;
            let mut prefixes: HashSet<i32> = HashSet::new();
            for &n in &nums {
                prefixes.insert(n & mask);
            }
            let candidate = best | (1 << bit);
            for &p in &prefixes {
                if prefixes.contains(&(candidate ^ p)) {
                    best= candidate;
                    break;
                }
            }
        }
        best
    }
}

Rust · runnable

function findMaximumXOR(nums: number[]): number {
  let best = 0;
  for (let bit = 30; bit >= 0; bit--) {
    const mask = ~((1 << bit) - 1);
    const prefixes = new Set<number>();
    for (const n of nums) prefixes.add(n & mask);
    const candidate = best | (1 << bit);
    for (const p of prefixes) {
      if (prefixes.has(candidate ^ p)) {
        best= candidate;
        break;
      }
    }
  }
  return best;
}

TypeScript · runnable

Bitwise Trie

TimeO(n · 31)

SpaceO(n · 31)

Recommended

Treat each integer as a string of 31 bits (ignoring the sign bit for nonneg inputs). Insert each into a binary trie keyed by bit value. To find the best partner for x, walk the trie from the highest bit down: at each step, prefer the child labeled with the opposite bit of x — that bit contributes 1 to the XOR. If the opposite child doesn't exist, take the same-bit child (that bit contributes 0). Accumulate the XOR as you walk.

This is the natural generalization of problem #208 (implement trie): swap a 26-alphabet for a 2-alphabet, swap character iteration for bit iteration.

#[derive(Default)]
struct BitTrie {
    children: [Option<Box<BitTrie>>; 2],
}

impl BitTrie {
    fn insert(&mut self, num: i32) {
        let mut node = self;
        for bit in (0..31).rev() {
            let b = ((num >> bit) & 1) as usize;
            node = node.children[b].get_or_insert_with(|| Box::new(BitTrie::default()));
        }
    }

    fn max_xor(&self, num: i32) -> i32 {
        let mut node = self;
        let mut acc = 0i32;
        for bit in (0..31).rev() {
            let b = ((num >> bit) & 1) as usize;
            let want = 1 - b;
            if let Some(child) = node.children[want].as_deref() {
                acc |= 1 << bit;
                node= child;
            } else if let Some(child)= node.children[b].as_deref() {
                node= child;
            } else {
                return acc;
            }
        }
        acc
    }
}

impl Solution {
    pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
        let mut trie = BitTrie::default();
        for &n in &nums {
            trie.insert(n);
        }
        let mut best = 0i32;
        for &n in &nums {
            best = best.max(trie.max_xor(n));
        }
        best
    }
}

Rust · runnable

class BitTrie {
  children: Array<BitTrie | null> = [null, null];

  insert(num: number): void {
    let node: BitTrie = this;
    for (let bit = 30; bit >= 0; bit--) {
      const b = (num >> bit) & 1;
      let next = node.children[b];
      if (next === null) {
        next = new BitTrie();
        node.children[b] = next;
      }
      node = next;
    }
  }

  maxXor(num: number): number {
    let node: BitTrie = this;
    let acc = 0;
    for (let bit = 30; bit >= 0; bit--) {
      const b = (num >> bit) & 1;
      const want = b ^ 1;
      if (node.children[want] !== null) {
        acc |= 1 << bit;
        node= node.children[want]!;
      } else if (node.children[b] = null) {
        node= node.children[b]!;
      } else {
        return acc;
      }
    }
    return acc;
  }
}

function findMaximumXOR(nums: number[]): number {
  const trie= new BitTrie();
  for (const n of nums) trie.insert(n);
  let best= 0;
  for (const n of nums) {
    const x= trie.maxXor(n);
    if (x > best) best = x;
  }
  return best;
}

TypeScript · runnable

Language notes:

Rust — the [Option<Box<T>>; 2] pattern mirrors the fixed-array trie in #208. as_deref() converts Option<Box<BitTrie>> into Option<&BitTrie> without re-borrowing.
TypeScript — no unsigned >>> needed because LeetCode's input is 0 ≤ nums[i] ≤ 2³¹ - 1, safely inside signed 32-bit range.

Trace

Greedy bit-by-bit on nums = [3, 10, 5, 25, 2, 8] — the bits matter up through bit 4 (25 = 11001₂). Each row shows one bit from high to low:

bit	prefixes	candidate	found pair?	best
4	{0, 0, 0, 16, 0, 0}	10000	yes (0, 16)	10000
3	{0, 8, 0, 24, 0, 8}	11000	yes (0, 24)	11000
2	{0, 8, 4, 24, 0, 8}	11100	yes (4, 24)	11100
1	{2, 10, 4, 24, 2, 8}	11110	no	11100
0	{3, 10, 5, 25, 2, 8}	11101	no	11100

Final best = 11100₂ = 28. The pair that achieved this is 5 XOR 25 = 28 — confirmed by prefix (4, 24) on bit 2.

Edge cases

Single element — only nums[0] exists, no pair; return 0. Both max_xor(n) on a trie holding only n and the empty greedy loop return 0.
All identical values — every pair XORs to 0; return 0.
Powers of two — [1, 2, 4, 8] gives 8 ^ 4 = 12 (best); illustrates that the highest set bit in the winner comes from the single largest value.
Zero present — 0 ^ x = x for any x, so the largest number in the array is always a candidate partner for 0.

Takeaway

XOR-extremum problems succumb to bit-greedy thinking plus a structure that answers "does the opposite bit exist at this level?". The hash-set method is a clever reformulation; the trie is the reusable tool.

Once you've built the bit trie here, problem #1707 ("max XOR with a limit") falls out as "same trie, sort queries by limit, insert numbers up to the limit before querying", and #1734 ("decode XORed perm") becomes much easier to think about.

Medium#208

Implement Trie

Build the basic trie. In Rust, use Vec<Option<Box<TrieNode>>> or arena alloc.

Hard#1707

Maximum XOR With an Element From Array

Offline sort + incremental trie insertion + XOR query.

Hard#1835

Find XOR Sum of All Pairs Bitwise AND

Pure bit-level reasoning. Think about each bit independently.