Maximum XOR of Two Numbers in an Array

Leetcode Problem 421: Maximum XOR of Two Numbers in an Array

Problem Summary

Given an integer array nums, find the largest XOR value obtainable by choosing two elements from the array (the same index can be chosen in the mathematical formulation with i <= j).

In practice, the goal is to maximize the bitwise XOR outcome across all valid pairs.

Constraints (descriptive):

The array has between 1 and 2 * 10^5 numbers.
Each number is a non-negative 32-bit integer in the range [0, 2^31 - 1].

Techniques

Array
Hash Table
Bit Manipulation
Trie

Solution

class TrieNodeNumber {
    constructor(
        public children: Map<number, TrieNodeNumber> = new Map()
    ) { }
}

class TrieXor {
    private root: TrieNodeNumber = new TrieNodeNumber()

    insert(num: number): void {
        let node = this.root

        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;

            if (!node.children.has(bit)) {
                node.children.set(bit, new TrieNodeNumber());
            }

            node =  node.children.get(bit)!;
        }
    }

    xor(num: number): number {
        let node = this.root;
        let maxXOR = 0;

        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const oppositeBit = 1 - bit;

            if (node.children.has(oppositeBit)) {
                maxXOR |= (1 << i);
                node = node.children.get(oppositeBit)!;
            } else {
                node =  node.children.get(bit)!;
            }
        }

        return maxXOR;
    }
}

function findMaximumXOR(nums: number[]): number {
    const search  = new TrieXor()
    let maxXor = 0

    search.insert(nums[0])

    for (let i = 1; i < nums.length; i++) {
        let currentNum = nums[i]
        let newXor = search.xor(currentNum)

        if (newXor > maxXor) {
            maxXor = newXor
        }

        search.insert(currentNum)
    }

    return maxXor
}

console.log(findMaximumXOR([3, 10, 5, 25, 2, 8])) // Output: 28