Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Trie

Guide 4 of 6 · Path 4 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtrie

Maximum XOR of Two Numbers in an Array

Problem (restated)

Given non-negative integers, return the maximum value of nums[i] XOR nums[j] (i may equal j).

Intuition

Build a binary trie of bits MSB→LSB. For each number, greedily walk opposite bits to maximize XOR.

Approaches

Binary bit trie

Tested only
Time O(32n)Space O(32n)

Idea. Insert then query (self-XOR is 0; better pairs appear after insert of both). Prefer opposite bit at each level.

Walkthrough. [3,10,5,25,2,8] → 28 (5 XOR 25).

Trade-offs. O(n^2) brute is fine for tiny n; trie is O(n) with 32-bit width.

Solution
type Node = { 0?: Node; 1?: Node };

export function findMaximumXOR(nums: number[]): number {
  const root: Node = {};
  const insert = (x: number) => {
    let n = root;
    for (let b = 31; b >= 0; b--) {
      const bit = ((x >> b) & 1) as 0 | 1;
      n[bit] ??= {};
      n = n[bit]!;
    }
  };
  const query = (x: number): number => {
    let n = root;
    let best = 0;
    for (let b = 31; b >= 0; b--) {
      const bit = (x >> b) & 1;
      const want = (1 - bit) as 0 | 1;
      if (n[want]) {
        best |= 1 << b;
        n = n[want]!;
      } else {
        n = n[bit as 0 | 1]!;
      }
    }
    return best;
  };
  let ans = 0;
  for (const x of nums) {
    insert(x);
    ans = Math.max(ans, query(x));
  }
  return ans;
}

type Node = { 0?: Node; 1?: Node };

export function findMaximumXOR(nums: number[]): number {
  const root: Node = {};
  const insert = (x: number) => {
    let n = root;
    for (let b = 31; b >= 0; b--) {
      const bit = ((x >> b) & 1) as 0 | 1;
      n[bit] ??= {};
      n = n[bit]!;
    }
  };
  const query = (x: number): number => {
    let n = root;
    let best = 0;
    for (let b = 31; b >= 0; b--) {
      const bit = (x >> b) & 1;
      const want = (1 - bit) as 0 | 1;
      if (n[want]) {
        best |= 1 << b;
        n = n[want]!;
      } else {
        n = n[bit as 0 | 1]!;
      }
    }
    return best;
  };
  let ans = 0;
  for (const x of nums) {
    insert(x);
    ans = Math.max(ans, query(x));
  }
  return ans;
}

Template connection

Trie over bit strings for greedy XOR.

Reflection