Maximum XOR With Element From Array

🎯

Maximum XOR With Element From Array

hardMIXEDGoogleAmazon

Imagine you have a database of encrypted keys and want to find the best key to unlock a device by maximizing the XOR with a given query, but only among keys that meet certain constraints.

💡 This problem combines bit manipulation with efficient data structures and offline query processing, which can be confusing for beginners because it requires understanding XOR properties, tries, and sorting queries to optimize lookups.

📋

Problem Statement

You are given an array nums of non-negative integers and an array queries where queries[i] = [x_i, m_i]. For each query i, find the maximum XOR value of x_i with any element in nums that is less than or equal to m_i. If no such element exists, return -1 for that query. Return an array answer where answer[i] is the answer to the i-th query.

1 ≤ nums.length, queries.length ≤ 10^50 ≤ nums[i], x_i, m_i ≤ 10^9

💡

Example

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

Output[3,3,7]

For query [3,1], elements ≤1 are [0,1], max XOR with 3 is 3 (3^0=3, 3^1=2). For [1,3], elements ≤3 are [0,1,2,3], max XOR with 1 is 3 (1^2=3). For [5,6], elements ≤6 are all nums, max XOR with 5 is 7 (5^2=7).

• No elements in nums are ≤ m_i → output -1
• All nums elements are zero → XOR results depend only on x_i
• Queries with x_i = 0 → max XOR is max element ≤ m_i
• Large nums and queries with maximum values (10^9) → test performance

⚠️

Common Mistakes

Not sorting queries and nums before processing

Leads to incorrect results or inefficient repeated insertions

✅ Sort nums and queries by m_i before processing

Forgetting to handle the case when no nums element ≤ m_i exists

Returns incorrect max XOR or crashes due to empty trie

✅ Check if trie is empty before querying and return -1 if so

Incorrect bit indexing in trie insertion or query

Wrong XOR results due to bit misalignment

✅ Always iterate from the highest bit (31) down to 0

Using brute force for large inputs

Time limit exceeded (TLE) in interviews

✅ Explain brute force but implement trie-based offline query solution

Not restoring answers to original query order after sorting

Output answers in wrong order, failing correctness

✅ Store original indices and reorder results before returning

🧠

Brute Force (Nested Loops)

💡 This approach exists to establish a baseline understanding by directly checking all possibilities, which helps grasp the problem's requirements and why naive methods are inefficient.

Intuition

For each query, check every element in nums that satisfies the constraint and compute XOR with x_i, then pick the maximum.

Algorithm

1. Initialize an answer array with -1 for each query.
2. For each query [x, m], iterate over all elements in nums.
3. If nums[j] ≤ m, compute XOR of nums[j] and x.
4. Update the answer for the query with the maximum XOR found.

💡 The nested loops make it easy to understand but hide the inefficiency that arises with large input sizes.

</>

Code

def maximizeXor(nums, queries):
    n = len(nums)
    res = []
    for x, m in queries:
        max_xor = -1
        for num in nums:
            if num <= m:
                max_xor = max(max_xor, x ^ num)
        res.append(max_xor)
    return res

# Example usage
if __name__ == '__main__':
    nums = [0,1,2,3,4]
    queries = [[3,1],[1,3],[5,6]]
    print(maximizeXor(nums, queries))

Line Notes

for x, m in queries:Iterate over each query to process independently

for num in nums:Check every number in nums for the current query

if num <= m:Only consider nums elements that satisfy the constraint

max_xor = max(max_xor, x ^ num)Update maximum XOR found for this query

import java.util.*;
public class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int[] res = new int[queries.length];
        Arrays.fill(res, -1);
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0], m = queries[i][1];
            for (int num : nums) {
                if (num <= m) {
                    res[i] = Math.max(res[i], x ^ num);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,2,3,4};
        int[][] queries = {{3,1},{1,3},{5,6}};
        System.out.println(Arrays.toString(sol.maximizeXor(nums, queries)));
    }
}

Line Notes

for (int i = 0; i < queries.length; i++) {Loop over each query index

int x = queries[i][0], m = queries[i][1];Extract x and m for current query

for (int num : nums) {Check all nums elements for this query

res[i] = Math.max(res[i], x ^ num);Update max XOR for this query

#include <bits/stdc++.h>
using namespace std;

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> res(queries.size(), -1);
    for (int i = 0; i < (int)queries.size(); i++) {
        int x = queries[i][0], m = queries[i][1];
        for (int num : nums) {
            if (num <= m) {
                res[i] = max(res[i], x ^ num);
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {0,1,2,3,4};
    vector<vector<int>> queries = {{3,1},{1,3},{5,6}};
    vector<int> ans = maximizeXor(nums, queries);
    for (int v : ans) cout << v << ' ';
    cout << '\n';
    return 0;
}

Line Notes

for (int i = 0; i < (int)queries.size(); i++) {Iterate over queries by index

int x = queries[i][0], m = queries[i][1];Extract query parameters

for (int num : nums) {Check all nums elements for this query

res[i] = max(res[i], x ^ num);Keep track of maximum XOR found

var maximizeXor = function(nums, queries) {
    let res = [];
    for (let [x, m] of queries) {
        let maxXor = -1;
        for (let num of nums) {
            if (num <= m) {
                maxXor = Math.max(maxXor, x ^ num);
            }
        }
        res.push(maxXor);
    }
    return res;
};

// Example usage
const nums = [0,1,2,3,4];
const queries = [[3,1],[1,3],[5,6]];
console.log(maximizeXor(nums, queries));

Line Notes

for (let [x, m] of queries) {Process each query by destructuring x and m

for (let num of nums) {Check every element in nums for the current query

if (num <= m) {Filter nums elements based on constraint

maxXor = Math.max(maxXor, x ^ num);Update maximum XOR for this query

⏱

Complexity

TimeO(n * q)

SpaceO(q)

For each of the q queries, we iterate over all n elements in nums, resulting in O(n*q) time. Space is O(q) for the output.

💡 If n and q are 10^5, this means 10^10 operations, which is too large to run in reasonable time.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Sorting + Offline Queries + Trie Insertion

💡 This approach introduces sorting and a bitwise trie to efficiently answer queries offline, which is a common technique to handle constraints and optimize lookups.

Intuition

Sort nums and queries by m_i, then incrementally insert nums elements into a trie as m_i increases, allowing quick max XOR queries for each x_i.

Algorithm

1. Sort nums in ascending order.
2. Sort queries by their m_i value, keeping track of original indices.
3. Initialize an empty bitwise trie.
4. Iterate over queries in ascending order of m_i, inserting all nums elements ≤ m_i into the trie.
5. For each query, find the maximum XOR of x_i with elements in the trie; if none, return -1.
6. Restore answers to original query order.

💡 Sorting queries and nums allows incremental trie building, avoiding repeated work and enabling efficient max XOR lookups.

</>

Code

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def maxXor(self, num):
        node = self.root
        if not node.children[0] and not node.children[1]:
            return -1
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if node.children[toggled_bit]:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

def maximizeXor(nums, queries):
    nums.sort()
    queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda x: x[1])
    trie = Trie()
    res = [-1] * len(queries)
    idx = 0
    n = len(nums)
    for x, m, i in queries:
        while idx < n and nums[idx] <= m:
            trie.insert(nums[idx])
            idx += 1
        res[i] = trie.maxXor(x)
    return res

# Example usage
if __name__ == '__main__':
    nums = [0,1,2,3,4]
    queries = [[3,1],[1,3],[5,6]]
    print(maximizeXor(nums, queries))

Line Notes

nums.sort()Sort nums to insert elements incrementally based on m_i

queries = sorted(..., key=lambda x: x[1])Sort queries by m_i to process in order

while idx < n and nums[idx] <= m:Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x)Query trie for max XOR with x_i among inserted nums

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) node.children[bit] = new TrieNode();
            node = node.children[bit];
        }
    }

    int maxXor(int num) {
        TrieNode node = root;
        if (node.children[0] == null && node.children[1] == null) return -1;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node.children[toggledBit] != null) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }
}

public class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int n = nums.length, q = queries.length;
        int[][] qWithIndex = new int[q][3];
        for (int i = 0; i < q; i++) {
            qWithIndex[i][0] = queries[i][0];
            qWithIndex[i][1] = queries[i][1];
            qWithIndex[i][2] = i;
        }
        Arrays.sort(qWithIndex, Comparator.comparingInt(a -> a[1]));
        Trie trie = new Trie();
        int[] res = new int[q];
        Arrays.fill(res, -1);
        int idx = 0;
        for (int[] query : qWithIndex) {
            int x = query[0], m = query[1], i = query[2];
            while (idx < n && nums[idx] <= m) {
                trie.insert(nums[idx]);
                idx++;
            }
            res[i] = trie.maxXor(x);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,2,3,4};
        int[][] queries = {{3,1},{1,3},{5,6}};
        System.out.println(Arrays.toString(sol.maximizeXor(nums, queries)));
    }
}

Line Notes

Arrays.sort(nums);Sort nums to insert incrementally based on m_i

Arrays.sort(qWithIndex, Comparator.comparingInt(a -> a[1]));Sort queries by m_i for offline processing

while (idx < n && nums[idx] <= m) {Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x);Query trie for max XOR with x_i among inserted nums

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    TrieNode* children[2] = {nullptr, nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) node->children[bit] = new TrieNode();
            node = node->children[bit];
        }
    }

    int maxXor(int num) {
        TrieNode* node = root;
        if (!node->children[0] && !node->children[1]) return -1;
        int max_xor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggled_bit = 1 - bit;
            if (node->children[toggled_bit]) {
                max_xor |= (1 << i);
                node = node->children[toggled_bit];
            } else {
                node = node->children[bit];
            }
        }
        return max_xor;
    }
};

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    int n = (int)nums.size(), q = (int)queries.size();
    vector<array<int,3>> qWithIndex(q);
    for (int i = 0; i < q; i++) {
        qWithIndex[i] = {queries[i][0], queries[i][1], i};
    }
    sort(qWithIndex.begin(), qWithIndex.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    Trie trie;
    vector<int> res(q, -1);
    int idx = 0;
    for (auto& query : qWithIndex) {
        int x = query[0], m = query[1], i = query[2];
        while (idx < n && nums[idx] <= m) {
            trie.insert(nums[idx]);
            idx++;
        }
        res[i] = trie.maxXor(x);
    }
    return res;
}

int main() {
    vector<int> nums = {0,1,2,3,4};
    vector<vector<int>> queries = {{3,1},{1,3},{5,6}};
    vector<int> ans = maximizeXor(nums, queries);
    for (int v : ans) cout << v << ' ';
    cout << '\n';
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort nums for incremental insertion

sort(qWithIndex.begin(), qWithIndex.end(), ...);Sort queries by m_i for offline processing

while (idx < n && nums[idx] <= m) {Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x);Query trie for max XOR with x_i among inserted nums

class TrieNode {
    constructor() {
        this.children = [null, null];
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            if (!node.children[bit]) node.children[bit] = new TrieNode();
            node = node.children[bit];
        }
    }

    maxXor(num) {
        let node = this.root;
        if (!node.children[0] && !node.children[1]) return -1;
        let maxXor = 0;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            let toggledBit = 1 - bit;
            if (node.children[toggledBit]) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }
}

var maximizeXor = function(nums, queries) {
    nums.sort((a,b) => a-b);
    let qWithIndex = queries.map((q,i) => [q[0], q[1], i]);
    qWithIndex.sort((a,b) => a[1] - b[1]);
    let trie = new Trie();
    let res = new Array(queries.length).fill(-1);
    let idx = 0;
    for (let [x, m, i] of qWithIndex) {
        while (idx < nums.length && nums[idx] <= m) {
            trie.insert(nums[idx]);
            idx++;
        }
        res[i] = trie.maxXor(x);
    }
    return res;
};

// Example usage
const nums = [0,1,2,3,4];
const queries = [[3,1],[1,3],[5,6]];
console.log(maximizeXor(nums, queries));

Line Notes

nums.sort((a,b) => a-b);Sort nums to insert incrementally based on m_i

qWithIndex.sort((a,b) => a[1] - b[1]);Sort queries by m_i for offline processing

while (idx < nums.length && nums[idx] <= m) {Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x);Query trie for max XOR with x_i among inserted nums

⏱

Complexity

TimeO((n + q) * log(maxNum))

SpaceO(n * log(maxNum))

Sorting nums and queries takes O(n log n + q log q). Each nums element is inserted once into the trie with depth ~32 bits, and each query is answered in O(log maxNum).

💡 For n and q up to 10^5 and 32-bit numbers, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted

This approach balances preprocessing and query answering efficiently, making it suitable for large inputs.

🧠

Optimized Bitwise Trie with Offline Queries and Two Pointers

💡 This approach refines the previous by carefully managing insertion and query order with two pointers, ensuring minimal overhead and maximum efficiency.

Intuition

By sorting nums and queries by m_i, we use a pointer to insert nums elements into the trie only once, then answer queries in order, avoiding repeated work and achieving optimal performance.

Algorithm

1. Sort nums and queries by m_i.
2. Initialize a bitwise trie and a pointer idx = 0 for nums.
3. For each query in ascending m_i order, insert all nums elements ≤ m_i into the trie using idx.
4. Query the trie for max XOR with x_i.
5. Store results in an array and return in original query order.

💡 The two-pointer technique ensures each nums element is inserted exactly once, and queries are answered in O(log maxNum) time.

</>

Code

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def maxXor(self, num):
        node = self.root
        if not node.children[0] and not node.children[1]:
            return -1
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if node.children[toggled_bit]:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

def maximizeXor(nums, queries):
    nums.sort()
    queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda x: x[1])
    trie = Trie()
    res = [-1] * len(queries)
    idx = 0
    n = len(nums)
    for x, m, i in queries:
        while idx < n and nums[idx] <= m:
            trie.insert(nums[idx])
            idx += 1
        res[i] = trie.maxXor(x)
    return res

# Example usage
if __name__ == '__main__':
    nums = [0,1,2,3,4]
    queries = [[3,1],[1,3],[5,6]]
    print(maximizeXor(nums, queries))

Line Notes

nums.sort()Sort nums to enable incremental insertion

queries = sorted(..., key=lambda x: x[1])Sort queries by m_i for offline processing

while idx < n and nums[idx] <= m:Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x)Query trie for max XOR with x_i among inserted nums

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) node.children[bit] = new TrieNode();
            node = node.children[bit];
        }
    }

    int maxXor(int num) {
        TrieNode node = root;
        if (node.children[0] == null && node.children[1] == null) return -1;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node.children[toggledBit] != null) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }
}

public class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int n = nums.length, q = queries.length;
        int[][] qWithIndex = new int[q][3];
        for (int i = 0; i < q; i++) {
            qWithIndex[i][0] = queries[i][0];
            qWithIndex[i][1] = queries[i][1];
            qWithIndex[i][2] = i;
        }
        Arrays.sort(qWithIndex, Comparator.comparingInt(a -> a[1]));
        Trie trie = new Trie();
        int[] res = new int[q];
        Arrays.fill(res, -1);
        int idx = 0;
        for (int[] query : qWithIndex) {
            int x = query[0], m = query[1], i = query[2];
            while (idx < n && nums[idx] <= m) {
                trie.insert(nums[idx]);
                idx++;
            }
            res[i] = trie.maxXor(x);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {0,1,2,3,4};
        int[][] queries = {{3,1},{1,3},{5,6}};
        System.out.println(Arrays.toString(sol.maximizeXor(nums, queries)));
    }
}

Line Notes

Arrays.sort(nums);Sort nums for incremental insertion

Arrays.sort(qWithIndex, Comparator.comparingInt(a -> a[1]));Sort queries by m_i for offline processing

while (idx < n && nums[idx] <= m) {Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x);Query trie for max XOR with x_i among inserted nums

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    TrieNode* children[2] = {nullptr, nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) node->children[bit] = new TrieNode();
            node = node->children[bit];
        }
    }

    int maxXor(int num) {
        TrieNode* node = root;
        if (!node->children[0] && !node->children[1]) return -1;
        int max_xor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggled_bit = 1 - bit;
            if (node->children[toggled_bit]) {
                max_xor |= (1 << i);
                node = node->children[toggled_bit];
            } else {
                node = node->children[bit];
            }
        }
        return max_xor;
    }
};

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    int n = (int)nums.size(), q = (int)queries.size();
    vector<array<int,3>> qWithIndex(q);
    for (int i = 0; i < q; i++) {
        qWithIndex[i] = {queries[i][0], queries[i][1], i};
    }
    sort(qWithIndex.begin(), qWithIndex.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    Trie trie;
    vector<int> res(q, -1);
    int idx = 0;
    for (auto& query : qWithIndex) {
        int x = query[0], m = query[1], i = query[2];
        while (idx < n && nums[idx] <= m) {
            trie.insert(nums[idx]);
            idx++;
        }
        res[i] = trie.maxXor(x);
    }
    return res;
}

int main() {
    vector<int> nums = {0,1,2,3,4};
    vector<vector<int>> queries = {{3,1},{1,3},{5,6}};
    vector<int> ans = maximizeXor(nums, queries);
    for (int v : ans) cout << v << ' ';
    cout << '\n';
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort nums for incremental insertion

sort(qWithIndex.begin(), qWithIndex.end(), ...);Sort queries by m_i for offline processing

while (idx < n && nums[idx] <= m) {Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x);Query trie for max XOR with x_i among inserted nums

class TrieNode {
    constructor() {
        this.children = [null, null];
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            if (!node.children[bit]) node.children[bit] = new TrieNode();
            node = node.children[bit];
        }
    }

    maxXor(num) {
        let node = this.root;
        if (!node.children[0] && !node.children[1]) return -1;
        let maxXor = 0;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            let toggledBit = 1 - bit;
            if (node.children[toggledBit]) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }
}

var maximizeXor = function(nums, queries) {
    nums.sort((a,b) => a-b);
    let qWithIndex = queries.map((q,i) => [q[0], q[1], i]);
    qWithIndex.sort((a,b) => a[1] - b[1]);
    let trie = new Trie();
    let res = new Array(queries.length).fill(-1);
    let idx = 0;
    for (let [x, m, i] of qWithIndex) {
        while (idx < nums.length && nums[idx] <= m) {
            trie.insert(nums[idx]);
            idx++;
        }
        res[i] = trie.maxXor(x);
    }
    return res;
};

// Example usage
const nums = [0,1,2,3,4];
const queries = [[3,1],[1,3],[5,6]];
console.log(maximizeXor(nums, queries));

Line Notes

nums.sort((a,b) => a-b);Sort nums for incremental insertion

qWithIndex.sort((a,b) => a[1] - b[1]);Sort queries by m_i for offline processing

while (idx < nums.length && nums[idx] <= m) {Insert all nums elements ≤ current query's m_i

res[i] = trie.maxXor(x);Query trie for max XOR with x_i among inserted nums

⏱

Complexity

TimeO((n + q) * log(maxNum))

SpaceO(n * log(maxNum))

Each nums element is inserted once into the trie, and each query is answered in O(log maxNum). Sorting takes O(n log n + q log q).

💡 This approach is optimal for large inputs, efficiently handling up to 10^5 queries and nums.

Interview Verdict: Accepted

This is the best practical approach combining sorting, tries, and offline queries for maximum XOR problems.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always mention brute force briefly, then implement the trie-based offline queries approach for best performance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * q)	O(q)	No	N/A	Mention only - never code for large inputs
2. Sorting + Offline Queries + Trie	O((n + q) * log(maxNum))	O(n * log(maxNum))	No	N/A	Code this approach for optimal performance
3. Optimized Trie with Two Pointers	O((n + q) * log(maxNum))	O(n * log(maxNum))	No	N/A	Preferred approach for best efficiency and clarity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs and optimizations clearly in interviews.

How to Present

Clarify the problem constraints and what XOR means.Start with the brute force approach to show understanding.Explain why brute force is inefficient for large inputs.Introduce sorting and offline queries to optimize.Describe the bitwise trie data structure and how it helps.Implement the trie-based solution with offline queries.Discuss time and space complexity and possible edge cases.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 15min → Test & Discuss: 10min. Total ~40min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, data structures (tries), offline query techniques, and your ability to optimize naive solutions.

Common Follow-ups

• What if nums or queries are extremely large? → Use tries and offline queries as shown.
• Can you optimize space usage? → Use iterative trie or bitset optimizations.

💡 These follow-ups test your ability to scale solutions and optimize memory, common in FAANG interviews.

🔍

Pattern Recognition

When to Use

1) You need to find max XOR with constraints; 2) Queries have constraints on elements; 3) Large input sizes require optimization; 4) Bitwise tries or offline queries can help.

Signature Phrases

maximum XOR with elementqueries with constraintsbitwise trie

NOT This Pattern When

Problems that only require prefix XOR or simple XOR without constraints are different and simpler.

Similar Problems

Maximum XOR of Two Numbers in an Array - similar use of tries for max XORXOR Queries of a Subarray - uses prefix XOR and queriesMaximum XOR With an Element From Array II - extension with dynamic updates

Practice

1. Given a string text and a list of words, you need to find all pairs of indices [i, j] such that the substring text[i:j+1] is in the list of words. Which approach guarantees an optimal solution in terms of time complexity when the list of words is large and words have varying lengths?

easy

A. Build a trie from the list of words and perform a DFS from each index in the text to find matching substrings.

B. Use dynamic programming to store whether substrings are in the word list and build results bottom-up.

C. Use a brute force nested loop to check every substring against the list of words directly.

D. Sort the list of words and use binary search to check each substring generated from the text.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding all substrings of text that match any word in a large list. Checking every substring against the list directly is expensive.

2. Step 2: Recognize the trie + DFS pattern

   Building a trie from the words allows prefix-based pruning. DFS from each index in text efficiently finds all matching substrings without redundant checks, guaranteeing optimal time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS prunes search space better than brute force or binary search [OK]

Hint: Trie + DFS prunes prefix search efficiently [OK]

Common Mistakes:

• Thinking brute force is efficient enough for large inputs

2. What is the time complexity of the optimal Trie + DFS with memoization solution for finding all concatenated words in a dictionary of n words with maximum length L?

medium

A. O(n * L^3) due to checking all substring splits recursively

B. O(n * L^2) because each word triggers DFS with memoization and Trie traversal

C. O(n^2 * L) since each word is compared against all others

D. O(n * L) as Trie insertion and lookup are linear in word length

Solution

1. Step 1: Identify outer loop over n words and inner DFS per word

   Each word triggers DFS that explores prefixes up to length L, with memoization preventing repeated work.

2. Step 2: Analyze DFS and Trie traversal costs

   DFS explores up to L positions, each prefix check is O(1) in Trie per character, total O(L^2) per word due to nested loops and memoization.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Memoization reduces exponential splits to O(L^2) per word, multiplied by n words [OK]

Hint: Memoization reduces exponential recursion to quadratic per word [OK]

Common Mistakes:

• Confusing brute force O(n*L^3) with optimized approach
• Ignoring memoization benefits

3. What is the time complexity of the optimal bitwise trie approach to count pairs with XOR in a range for an input array of size n and maximum number M (max element)?

medium

A. O(n * log M)

B. O(n^2)

C. O(n * M)

D. O(n * log n)

Solution

1. Step 1: Identify operations per element

   Each number is inserted into the trie in O(log M) time, where M is the max number (bit length).

2. Step 2: Query per element also takes O(log M)

   For each number, querying the trie for counts less than a limit also takes O(log M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n * log M) due to insert and query per element [OK]

Hint: Trie operations scale with bit length, not array size squared [OK]

Common Mistakes:

• Assuming O(n^2) due to pairs
• Confusing M with n in complexity
• Ignoring log factor from bit length

4. Examine the following buggy snippet from the Trie + DFS solution. Which line contains the subtle bug that can cause incorrect results or infinite loops?

def dfs(r, c, node):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    char = board[r][c]
    if char == '#' or char not in node.children:
        return
    node = node.children[char]
    if node.word:
        result.append(node.word)
        node.word = None
    # BUG: Missing marking visited cell
    dfs(r+1, c, node)
    dfs(r-1, c, node)
    dfs(r, c+1, node)
    dfs(r, c-1, node)
    # BUG: Missing restoring cell after DFS

medium

A. Line checking if char == '#' or char not in node.children

B. Lines calling dfs recursively without marking visited cells

C. Line appending node.word to result and setting node.word = None

D. Line updating node = node.children[char]

Solution

1. Step 1: Identify missing visited cell marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits and potential infinite loops.

2. Step 2: Identify missing restoring cell state

   Without restoring the cell after DFS, subsequent searches see corrupted board state, causing incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing visited marking causes infinite loops or incorrect word detection [OK]

Hint: Always mark and restore visited cells in DFS [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not restoring board state after DFS
• Appending duplicates without clearing node.word

5. Suppose the WordDictionary is extended to support searching for words with the wildcard '*' that matches zero or more characters (instead of '.' matching exactly one). Which of the following modifications to the trie search algorithm correctly handles '*' wildcard searches?

hard

A. Use recursion or stack to explore zero or more characters by branching at current node and advancing index accordingly.

B. Treat '*' as '.' and continue with single character branching only.

C. Precompute all possible expansions of '*' and store them in the trie during addWord.

D. Ignore '*' and treat it as a literal character during search.

Solution

1. Step 1: Understand '*' wildcard semantics

   '*' matches zero or more characters, so search must explore skipping '*' or consuming characters.

2. Step 2: Identify correct search strategy

   Using recursion or stack to explore both skipping '*' (index+1) and consuming children (index unchanged) correctly handles zero or more matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Branching on both skipping and consuming characters handles '*' wildcard [OK]

Hint: '*' requires branching on skip or consume [OK]

Common Mistakes:

• Treating '*' like '.'
• Precomputing expansions is infeasible
• Ignoring '*' wildcard semantics