Maximum xor of two numbers in an array

Array Hash Table Bit Manipulation Trie

53.4% acceptance

Jan 13, 2026

5916

422

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

struct TrieNode {
  children: [Option<Box<TrieNode>>; 2],
}

impl TrieNode {
  fn new() -> Self {
    TrieNode { children: [None, None] }
  }
}

impl Solution {
  pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
    let mut root = TrieNode::new();
    
    for &num in &nums {
      let mut node = &mut root;
      for i in (0..31).rev() {
        let bit = ((num >> i) & 1) as usize;
        if node.children[bit].is_none() {
          node.children[bit] = Some(Box::new(TrieNode::new()));
        }
        node = node.children[bit].as_mut().unwrap();
      }
    }
    
    let mut max_xor = 0;
    for &num in &nums {
      let mut node = &root;
      let mut current_xor = 0;
      
      for i in (0..31).rev() {
        let bit = ((num >> i) & 1) as usize;
        let toggle = 1 - bit;
        
        if node.children[toggle].is_some() {
          current_xor |= 1 << i;
          node = node.children[toggle].as_ref().unwrap();
        } else {
          node = node.children[bit].as_ref().unwrap();
        }
      }
      
      max_xor = max_xor.max(current_xor);
    }
    
    max_xor
  }
}