Stage 4: Advanced Techniques·Trie & Bitwise

Hard#17079 min readTrieBit ManipulationSortingLeetCode

Maximum XOR With an Element From Array

Offline queries with bitwise trie

Offline sort + incremental trie insertion + XOR query.

Published Apr 16, 2026

Problem

Given an array nums and queries queries[i] = [x_i, m_i], for each query find the maximum XOR of x_i with any element of nums that is <= m_i. If no such element exists, answer -1.

Input

nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]]

Output

[3, 3, 7]

Explanation

Query [3,1]: eligible {0,1}. 3^0=3, 3^1=2. Max=3. Query [1,3]: eligible {0,1,2,3}. 1^3=2, 1^2=3. Max=3. Query [5,6]: eligible all. 5^2=7. Max=7.

Input

nums = [5, 2, 4, 6, 6, 3], queries = [[12, 4], [8, 1], [6, 3]]

Output

[15, -1, 5]

Explanation

Query [12,4]: eligible {2,4,3}. 12^3=15. Query [8,1]: only eligible is nothing (no element <=1 in this set). Actually 2>1, 4>1, etc. → -1. Query [6,3]: eligible {2,3}. 6^3=5.

Intuition

Problem #421 solves "max XOR of any pair" using a bitwise trie in O(n log V). This extends it with a per-query limit.

Offline trick: sort nums ascending and sort queries by m_i ascending. Process queries in order: before answering query (x_i, m_i), insert all nums[j] <= m_i into the trie. Then query the trie for maximum XOR with x_i.

Each element enters the trie once. Each query walks the trie once. Total: O((n + q) * 30) where 30 is the bit width.

Interactive concept

Offline XOR Trie Queries

Sort queries by limit mi; insert nums into a binary trie only when nums <= mi.

Sort by limit

Queries with smaller mi see a prefix of the sorted nums array.

nums sorted

[0,1,2,3,4]

query mi=1

insert 0,1

query mi=3

insert 2,3

Approach

Brute Force

TimeO(q · n)

SpaceO(1)

For each query, scan all nums and compute XOR with eligible elements.

impl Solution {
    pub fn maximize_xor(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        queries
            .iter()
            .map(|q| {
                let (x, m) = (q[0], q[1]);
                let mut best = -1i32;
                for &v in &nums {
                    if v <= m {
                        best= best.max(x ^ v);
                    }
                }
                best
            })
            .collect()
    }
}

Rust · runnable

function maximizeXor(nums: number[], queries: number[][]): number[] {
  return queries.map(([x, m]) => {
    let best = -1;
    for (const v of nums) {
      if (v <= m) best = Math.max(best, x ^ v);
    }
    return best;
  });
}

TypeScript · runnable

Offline Queries + Bitwise Trie

TimeO((n + q) · 30)

SpaceO(n · 30)

Recommended

Sort nums. Sort queries by m_i (keep original indices). Incrementally insert into a binary trie (MSB to LSB, 30 bits). For each query, greedily walk opposite bits.

impl Solution {
    pub fn maximize_xor(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        nums.sort_unstable();

        let q = queries.len();
        let mut idx: Vec<usize> = (0..q).collect();
        idx.sort_by_key(|&i| queries[i][1]);

        // Binary trie: each node is [left_child, right_child] index into `nodes`.
        // -1 means absent.
        let mut nodes: Vec<[i32; 2]> = vec![[-1, -1]]; // root = 0.

        let mut ans = vec![-1i32; q];
        let mut ni = 0; // pointer into sorted nums.

        for &qi in &idx {
            let x = queries[qi][0];
            let m = queries[qi][1];

            // Insert all nums[ni] <= m.
            while ni < nums.len() && nums[ni] <= m {
                let mut cur= 0usize;
                for b in (0..30).rev() {
                    let bit= ((nums[ni] >> b) & 1) as usize;
                    if nodes[cur][bit] < 0 {
                        nodes.push([-1, -1]);
                        nodes[cur][bit]= (nodes.len() - 1) as i32;
                    }
                    cur= nodes[cur][bit] as usize;
                }
                ni = 1;
            }

            // Query: greedily pick opposite bit.
            if ni= 0 {
                ans[qi]= -1;
                continue;
            }
            let mut cur= 0usize;
            let mut xor_val= 0i32;
            for b in (0..30).rev() {
                let want= ((x >> b) & 1) as usize ^ 1;
                if nodes[cur][want] >= 0 {
                    xor_val |= 1 << b;
                    cur= nodes[cur][want] as usize;
                } else {
                    cur= nodes[cur][want ^ 1] as usize;
                }
            }
            ans[qi]= xor_val;
        }

        ans
    }
}

Rust · runnable

function maximizeXor(nums: number[], queries: number[][]): number[] {
  nums.sort((a, b) => a - b);

  const q = queries.length;
  const idx = Array.from({ length: q }, (_, i) => i);
  idx.sort((a, b) => queries[a][1] - queries[b][1]);

  // Binary trie: nodes[i] = [left, right], -1 = absent.
  const nodes: Array<[number, number]> = [[-1, -1]];

  const ans = new Array<number>(q).fill(-1);
  let ni = 0;

  for (const qi of idx) {
    const [x, m] = queries[qi];

    while (ni < nums.length && nums[ni] <= m) {
      let cur= 0;
      for (let b= 29; b >= 0; b--) {
        const bit = (nums[ni] >> b) & 1;
        if (nodes[cur][bit] < 0) {
          nodes.push([-1, -1]);
          nodes[cur][bit]= nodes.length - 1;
        }
        cur= nodes[cur][bit];
      }
      ni++;
    }

    if (ni= 0) { ans[qi]= -1; continue; }

    let cur= 0;
    let xorVal= 0;
    for (let b= 29; b >= 0; b--) {
      const want = ((x >> b) & 1) ^ 1;
      if (nodes[cur][want] >= 0) {
        xorVal |= 1 << b;
        cur= nodes[cur][want];
      } else {
        cur= nodes[cur][want ^ 1];
      }
    }
    ans[qi]= xorVal;
  }

  return ans;
}

TypeScript · runnable

Trace

nums = [0, 1, 2, 3, 4], queries sorted by m: [[3,1],[1,3],[5,6]]:

Bitwise/trie#1707

Maximum XOR With an Element From Array walkthrough

nums = [0,1,2,3,4], queries sorted by m

Step 1 of 30%

Bitwise/trie state

m = 1

For query [3,1], only 0 and 1 are eligible.

Insert eligible numbers lazily

Decision

Advance the nums pointer while nums[p] <= m.

Update

Trie contains {0,1}.

Why it works

Offline sorting avoids rebuilding the trie per query.

Edge cases

No eligible elements — all nums > m. Return -1.
m = 0 — only nums values of 0 are eligible.
x = 0 — XOR with anything returns the value itself; max is the largest eligible element.
Single nums element — trie is a single path; no branching during query.

Takeaway

Offline sorting + incremental data structure is the standard trick when queries have a threshold parameter. Sort both the data and the queries by that threshold, advance a pointer. The trie itself is reusable from #421 — the only addition is the offline wrapper.

Medium#421

Maximum XOR of Two Numbers in Array

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

Medium#208

Implement Trie

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

Hard#1835

Find XOR Sum of All Pairs Bitwise AND

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