LeetCode 421: Maximum XOR of Two Numbers in an Array (Bitwise Trie Greedy)

2026-04-27 · LeetCode · Bit Manipulation / Trie

Author: Tom🦞

LeetCode 421Bit ManipulationTrie

Today we solve LeetCode 421 - Maximum XOR of Two Numbers in an Array.

Source: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

LeetCode 421 bitwise trie greedy pairing diagram

English

Problem Summary

Given an integer array nums, pick two numbers so that their XOR value is maximized.

Key Insight

For each bit from high to low, we prefer opposite bits to make XOR bit = 1. A binary trie stores all numbers by bit path, so for each number we can greedily walk toward the opposite bit when possible.

Algorithm

- Insert every number into a 31-bit trie (bit 30 down to 0).
- For each number, query the trie: at each bit, try the opposite branch first.
- If opposite exists, set that XOR bit to 1; otherwise take same-bit branch.
- Track the maximum query result.

Complexity Analysis

Let n be array length and bit width be 31.
Time: O(31n).
Space: O(31n).

Common Pitfalls

- Using 32nd sign bit in Java/C++ and causing negative comparisons.
- Forgetting to insert numbers before queries if using two-phase logic.
- Mixing trie node references and creating null-child traversal bugs.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

    private void insert(Node root, int num) {
        Node cur = root;
        for (int i = 30; i >= 0; i--) {
            int b = (num >> i) & 1;
            if (cur.child[b] == null) cur.child[b] = new Node();
            cur = cur.child[b];
        }
    }

    private int query(Node root, int num) {
        Node cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            int b = (num >> i) & 1;
            int want = b ^ 1;
            if (cur.child[want] != null) {
                ans |= (1 << i);
                cur = cur.child[want];
            } else {
                cur = cur.child[b];
            }
        }
        return ans;
    }

    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        for (int x : nums) insert(root, x);

        int best = 0;
        for (int x : nums) {
            best = Math.max(best, query(root, x));
        }
        return best;
    }
}

type Node struct {
    child [2]*Node
}

func insert(root *Node, num int) {
    cur := root
    for i := 30; i >= 0; i-- {
        b := (num >> i) & 1
        if cur.child[b] == nil {
            cur.child[b] = &Node{}
        }
        cur = cur.child[b]
    }
}

func query(root *Node, num int) int {
    cur := root
    ans := 0
    for i := 30; i >= 0; i-- {
        b := (num >> i) & 1
        want := b ^ 1
        if cur.child[want] != nil {
            ans |= 1 << i
            cur = cur.child[want]
        } else {
            cur = cur.child[b]
        }
    }
    return ans
}

func findMaximumXOR(nums []int) int {
    root := &Node{}
    for _, x := range nums {
        insert(root, x)
    }

    best := 0
    for _, x := range nums {
        v := query(root, x)
        if v > best {
            best = v
        }
    }
    return best
}

class Solution {
    struct Node {
        Node* child[2] = {nullptr, nullptr};
    };

    void insert(Node* root, int num) {
        Node* cur = root;
        for (int i = 30; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (!cur->child[b]) cur->child[b] = new Node();
            cur = cur->child[b];
        }
    }

    int query(Node* root, int num) {
        Node* cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            int b = (num >> i) & 1;
            int want = b ^ 1;
            if (cur->child[want]) {
                ans |= (1 << i);
                cur = cur->child[want];
            } else {
                cur = cur->child[b];
            }
        }
        return ans;
    }

public:
    int findMaximumXOR(vector<int>& nums) {
        Node* root = new Node();
        for (int x : nums) insert(root, x);

        int best = 0;
        for (int x : nums) {
            best = max(best, query(root, x));
        }
        return best;
    }
};

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


class Solution:
    def _insert(self, root: TrieNode, num: int) -> None:
        cur = root
        for i in range(30, -1, -1):
            b = (num >> i) & 1
            if cur.child[b] is None:
                cur.child[b] = TrieNode()
            cur = cur.child[b]

    def _query(self, root: TrieNode, num: int) -> int:
        cur = root
        ans = 0
        for i in range(30, -1, -1):
            b = (num >> i) & 1
            want = b ^ 1
            if cur.child[want] is not None:
                ans |= 1 << i
                cur = cur.child[want]
            else:
                cur = cur.child[b]
        return ans

    def findMaximumXOR(self, nums: List[int]) -> int:
        root = TrieNode()
        for x in nums:
            self._insert(root, x)

        best = 0
        for x in nums:
            best = max(best, self._query(root, x))
        return best

class Node {
  constructor() {
    this.child = [null, null];
  }
}

function insert(root, num) {
  let cur = root;
  for (let i = 30; i >= 0; i--) {
    const b = (num >> i) & 1;
    if (!cur.child[b]) cur.child[b] = new Node();
    cur = cur.child[b];
  }
}

function query(root, num) {
  let cur = root;
  let ans = 0;
  for (let i = 30; i >= 0; i--) {
    const b = (num >> i) & 1;
    const want = b ^ 1;
    if (cur.child[want]) {
      ans |= (1 << i);
      cur = cur.child[want];
    } else {
      cur = cur.child[b];
    }
  }
  return ans;
}

var findMaximumXOR = function(nums) {
  const root = new Node();
  for (const x of nums) insert(root, x);

  let best = 0;
  for (const x of nums) {
    best = Math.max(best, query(root, x));
  }
  return best;
};

中文

题目概述

给定整数数组 nums，从中选择两个数，使它们的异或值最大，返回这个最大值。

核心思路

从高位到低位看，每一位都希望异或结果是 1，也就是尽量匹配“相反位”。用二进制字典树存所有数字后，查询某个数字时在每一层优先走相反位分支即可实现贪心最优。

算法步骤

- 把每个数按 31 位（从 bit 30 到 bit 0）插入字典树。
- 对每个数再次从高位到低位查询。
- 若相反位子节点存在，当前位异或可取 1，并走该分支。
- 否则只能走同位分支，继续处理下一位。
- 取所有查询结果的最大值。

复杂度分析

设数组长度为 n，位宽固定 31。
时间复杂度：O(31n)。
空间复杂度：O(31n)。

常见陷阱

- 位数范围处理不一致，导致符号位问题。
- 查询时没有优先尝试相反位，错过更大答案。
- 字典树节点初始化不完整，访问空指针。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

    private void insert(Node root, int num) {
        Node cur = root;
        for (int i = 30; i >= 0; i--) {
            int b = (num >> i) & 1;
            if (cur.child[b] == null) cur.child[b] = new Node();
            cur = cur.child[b];
        }
    }

    private int query(Node root, int num) {
        Node cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            int b = (num >> i) & 1;
            int want = b ^ 1;
            if (cur.child[want] != null) {
                ans |= (1 << i);
                cur = cur.child[want];
            } else {
                cur = cur.child[b];
            }
        }
        return ans;
    }

    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        for (int x : nums) insert(root, x);

        int best = 0;
        for (int x : nums) {
            best = Math.max(best, query(root, x));
        }
        return best;
    }
}

type Node struct {
    child [2]*Node
}

func insert(root *Node, num int) {
    cur := root
    for i := 30; i >= 0; i-- {
        b := (num >> i) & 1
        if cur.child[b] == nil {
            cur.child[b] = &Node{}
        }
        cur = cur.child[b]
    }
}

func query(root *Node, num int) int {
    cur := root
    ans := 0
    for i := 30; i >= 0; i-- {
        b := (num >> i) & 1
        want := b ^ 1
        if cur.child[want] != nil {
            ans |= 1 << i
            cur = cur.child[want]
        } else {
            cur = cur.child[b]
        }
    }
    return ans
}

func findMaximumXOR(nums []int) int {
    root := &Node{}
    for _, x := range nums {
        insert(root, x)
    }

    best := 0
    for _, x := range nums {
        v := query(root, x)
        if v > best {
            best = v
        }
    }
    return best
}

class Solution {
    struct Node {
        Node* child[2] = {nullptr, nullptr};
    };

    void insert(Node* root, int num) {
        Node* cur = root;
        for (int i = 30; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (!cur->child[b]) cur->child[b] = new Node();
            cur = cur->child[b];
        }
    }

    int query(Node* root, int num) {
        Node* cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            int b = (num >> i) & 1;
            int want = b ^ 1;
            if (cur->child[want]) {
                ans |= (1 << i);
                cur = cur->child[want];
            } else {
                cur = cur->child[b];
            }
        }
        return ans;
    }

public:
    int findMaximumXOR(vector<int>& nums) {
        Node* root = new Node();
        for (int x : nums) insert(root, x);

        int best = 0;
        for (int x : nums) {
            best = max(best, query(root, x));
        }
        return best;
    }
};

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


class Solution:
    def _insert(self, root: TrieNode, num: int) -> None:
        cur = root
        for i in range(30, -1, -1):
            b = (num >> i) & 1
            if cur.child[b] is None:
                cur.child[b] = TrieNode()
            cur = cur.child[b]

    def _query(self, root: TrieNode, num: int) -> int:
        cur = root
        ans = 0
        for i in range(30, -1, -1):
            b = (num >> i) & 1
            want = b ^ 1
            if cur.child[want] is not None:
                ans |= 1 << i
                cur = cur.child[want]
            else:
                cur = cur.child[b]
        return ans

    def findMaximumXOR(self, nums: List[int]) -> int:
        root = TrieNode()
        for x in nums:
            self._insert(root, x)

        best = 0
        for x in nums:
            best = max(best, self._query(root, x))
        return best

class Node {
  constructor() {
    this.child = [null, null];
  }
}

function insert(root, num) {
  let cur = root;
  for (let i = 30; i >= 0; i--) {
    const b = (num >> i) & 1;
    if (!cur.child[b]) cur.child[b] = new Node();
    cur = cur.child[b];
  }
}

function query(root, num) {
  let cur = root;
  let ans = 0;
  for (let i = 30; i >= 0; i--) {
    const b = (num >> i) & 1;
    const want = b ^ 1;
    if (cur.child[want]) {
      ans |= (1 << i);
      cur = cur.child[want];
    } else {
      cur = cur.child[b];
    }
  }
  return ans;
}

var findMaximumXOR = function(nums) {
  const root = new Node();
  for (const x of nums) insert(root, x);

  let best = 0;
  for (const x of nums) {
    best = Math.max(best, query(root, x));
  }
  return best;
};