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 the following LFUCache implementation, what is the return value of cache.get(2) after executing the sequence below?

cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)

easy

A. 1

B. 3

C. 2

D. -1

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys 1 and 2 with freq=1. get(1) increments freq of key 1 to 2. Then put(3,3) triggers eviction: key 2 has freq=1, key 1 has freq=2, so key 2 is evicted. Key 3 inserted with freq=1.

2. Step 2: Evaluate get(2)

   Key 2 was evicted, so get(2) returns -1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Eviction removed key 2 -> get(2) returns -1 [OK]

Hint: Eviction removes least freq and LRU key -> get returns -1 [OK]

Common Mistakes:

• Assuming key 2 still exists after eviction
• Confusing frequency increments
• Off-by-one in frequency updates

2. Consider the following Python code implementing the optimal solution for the envelope nesting problem. Given the input [[5,4],[6,4],[6,7],[2,3]], what is the value of the tails list after processing all heights?

easy

A. [3, 4, 7]

B. [3, 4]

C. [2, 3, 4, 7]

D. [2, 3, 7]

Solution

1. Step 1: Sort envelopes and extract heights

   Sorted envelopes: [[2,3],[5,4],[6,7],[6,4]] -> heights = [3,4,7,4]

2. Step 2: Trace tails updates

   Insert 3 -> tails=[3]; Insert 4 -> tails=[3,4]; Insert 7 -> tails=[3,4,7]; Insert 4 replaces tails[1] -> tails=[3,4,7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final tails length is 3 with values [3,4,7] [OK]

Hint: Trace tails updates carefully with bisect_left [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Not replacing tails element on equal height
• Misordering envelopes before LIS

3. What is the time complexity of the single pass stack-based solution for the Largest Rectangle in Histogram problem, and why might a candidate mistakenly think it is higher?

medium

A. O(n) because each bar is pushed and popped at most once

B. O(n log n) due to sorting or binary search steps

C. O(n^2) because each bar can be pushed and popped multiple times

D. O(n) but with O(n^2) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze push/pop operations

   Each bar index is pushed onto the stack once and popped once when a smaller height is encountered, so total stack operations are O(n).

2. Step 2: Understand why complexity is linear

   Since the inner while loop pops bars only when a smaller height is found, total pops across all iterations sum to at most n, making the overall time O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Push/pop per bar once -> linear time [OK]

Hint: Each bar pushed and popped once -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing stack operations as repeated for each iteration
• Thinking recursion or sorting is involved

4. What is the time complexity of the optimal binary search partition approach to find the median of two sorted arrays of sizes m and n (m ≤ n)?

medium

A. O(log(min(m, n)))

B. O(m + n)

C. O(log(m + n))

D. O(log(m))

Solution

1. Step 1: Identify which array is binary searched

   The algorithm always binary searches the smaller array of size m.

2. Step 2: Analyze binary search complexity

   Binary search on array of size m takes O(log m) time. Since m ≤ n, this is O(log(min(m, n))).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on smaller array yields O(log(min(m,n))) [OK]

Hint: Binary search on smaller array size defines complexity [OK]

Common Mistakes:

• Assuming O(m + n) due to merging intuition
• Confusing log(m + n) with log(min(m, n))
• Ignoring that binary search is only on smaller array

5. If the data stream allows duplicate numbers to be removed arbitrarily after insertion, which modification to the two-heap median finder is necessary to maintain correct median retrieval?

hard

A. Implement lazy removal with a hash map to mark elements for delayed deletion and prune heaps accordingly.

B. Use a balanced binary search tree instead of heaps to allow efficient removals.

C. Re-sort the entire data structure after each removal to maintain order.

D. Keep all elements in a single min heap and remove duplicates by scanning.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals; removing elements directly breaks heap property or is costly.

2. Step 2: Lazy removal approach

   Mark elements to remove in a hash map and prune them lazily when they reach the top of heaps, maintaining heap structure and O(log n) operations.

3. Step 3: Evaluate other options

   Balanced BST (B) supports removals but median retrieval is not O(1). Re-sorting (C) is inefficient. Single min heap (D) cannot maintain median correctly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Lazy removal with hash map preserves heap efficiency and correctness [OK]

Hint: Lazy removal with hash map enables efficient arbitrary removals [OK]

Common Mistakes:

• Trying to remove elements directly from heaps
• Re-sorting after each removal
• Using single heap losing median property