Trie — Maximum XOR With an Element From Array

↗ LeetCode: Maximum XOR With an Element From Array · Hard · pattern chapter →

Asked atGoogleAmazon

Given nums and queries [query_val, max_allowed]. For each query return the max XOR of query_val with any x ∈ nums where x ≤ max_allowed. Return -1 if no such x.

Example — nums=[0,1,2,3,4], queries=[[3,1],[1,3],[5,6]] → [3,3,7]

Constraints — 1 ≤ n ≤ 10⁵; nums, queries ≤ 10⁵. Brute checks every pair — O(n·q) = 10¹⁰ ops at n=q=10⁵ (TLE). Offline sort + bit-trie insert-and-query is O((n+q)·31) = ~10⁶ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Linear per query

O(n · Q). TLE.

Approach 2 — Offline sort + binary trie (canonical)

Insight. Sort nums ascending; sort queries by max_allowed. Process queries in order, inserting nums into a binary trie as they become eligible. For each query, walk the trie greedily choosing the opposite bit.

class Node { Node[] c = new Node[2]; }
int[] maximizeXor(int[] nums, int[][] queries) {
    Arrays.sort(nums);
    Integer[] ord = new Integer[queries.length];
    for (int i = 0; i < queries.length; i++) ord[i] = i;
    Arrays.sort(ord, (a, b) -> queries[a][1] - queries[b][1]);
    int[] ans = new int[queries.length];
    Node root = new Node();
    int idx = 0;
    for (int qi : ord) {
        int v = queries[qi][0], cap = queries[qi][1];
        while (idx < nums.length && nums[idx] <= cap) insert(root, nums[idx++]);
        ans[qi] = idx == 0 ? -1 : maxXor(root, v);
    }
    return ans;
}
void insert(Node root, int x) {
    Node cur = root;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (cur.c[b] == null) cur.c[b] = new Node();
        cur = cur.c[b];
    }
}
int maxXor(Node root, int v) {
    Node cur = root; int r = 0;
    for (int i = 31; i >= 0; i--) {
        int b = (v >> i) & 1, want = 1 - b;
        if (cur.c[want] != null) { r |= 1 << i; cur = cur.c[want]; }
        else cur = cur.c[b];
    }
    return r;
}

Execution Trace

Linear per query

Step 1 / 3Initialize scan.

Complexity — Time O((n + q) · 32 + q log q); Space O(n · 32).

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Linear per query	O(n · Q)	O(1)	TLE
Offline sort + binary trie	O((n+q)·32)	O(n·32)	canonical

When to use which

• Max XOR queries → binary trie always.
• Constraint on element → offline sort processes queries in order of constraint.
• Streaming → online trie without deletion; harder with ≤ max constraint.

✨AI Study CompanionBeta

Related problems

• Maximum XOR of Two Numbers — offline sibling
• Count Pairs With XOR in Range
• Maximum Genetic Difference Query

Was this page helpful?