Log inSign up
hardLeetCodeNot Started

Maximum XOR With an Element From Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

You are given an array nums consisting of non-negative integers. You are also given a 2D array queries where queries[i] = [x_i, m_i].

The answer to the i-th query is the maximum bitwise XOR value of x_i and any nums[j] such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer[i] is the answer to the i-th query.

Example 1 · Example 1: Multiple threshold queries:

Input: nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]]
Output: [3, 3, 7]
Explanation: 1. Query [3, 1]: numbers <= 1 are [0, 1]. Max XOR = 3 ^ 0 = 3. 2. Query [1, 3]: numbers <= 3 are [0, 1, 2, 3]. Max XOR = 1 ^ 2 = 3. 3. Query [5, 6]: numbers <= 6 are all [0, 1, 2, 3, 4]. Max XOR = 5 ^ 2 = 7.

Constraints:

  • 1 <= nums.length, queries.length <= 105
  • queries[i].length == 2
  • 0 <= nums[j], x_i, m_i <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the technique of offline query sorting to convert static queries into monotonic insertions.
  • Combine two-pointer incremental loading with a Binary Trie.
  • Handle edge cases where no elements satisfy the constraint (returning -1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • XOR query constrained by an upper bound inequality nums[j] <= m_i.
  • Queries are given upfront and can be reordered (offline querying).
  • Multiple queries with varying thresholds.

Algorithmic Decision Tree:

  • Tag queries with original 0-indexed positions [m_i, x_i, original_index] and sort by m_i.
  • Sort nums in ascending order.
  • Maintain a two-pointer insert into a Binary Trie: insert elements while nums[ptr] <= m_i.

Connected Patterns:

Maximum XOR of Two Numbers in an ArrayRange XOR QueriesOffline Processing

1. Per-Query Linear Scan

Intuition

Loop over each query [x, m]. Initialize maxXor = -1. Loop through all numbers in nums. If num <= m, update maxXor = max(maxXor, x ^ num). Append maxXor to output.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Loop each query [x, m].
  2. Step 2: Initialize currMax = -1.
  3. Step 3: For each num in nums: if num <= m, update currMax = max(currMax, x ^ num).
  4. Step 4: Append currMax to result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
9 vector<int> ans;
10 for (const auto& q : queries) {
11 int x = q[0], m = q[1];
12 int currMax = -1;
13 for (int num : nums) {
14 if (num <= m) {
15 currMax = max(currMax, x ^ num);
16 }
17 }
18 ans.push_back(currMax);
19 }
20 return ans;
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<int> nums = {0, 1, 2, 3, 4};
27 vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};
28 auto res = sol.maximizeXor(nums, queries);
29 for (int v : res) cout << v << " ";
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(Q * N) — Must iterate all N numbers for each of the Q queries.
  • Space complexity: O(1) — Stores output array.

Why Brute Force Doesn't Scale:

With 100,000 queries and 100,000 numbers, checking all valid numbers times out by several orders of magnitude.

Offline sorting loads each element into the Trie once, answering all 100,000 queries in ~120ms.

2. Sorted Array Binary Search Range Scan

Intuition

Sort nums. For query [x, m], if nums[0] > m, return -1. Binary search finds the count of elements <= m. Scan those elements and compute max XOR.

When to apply: When m is typically very small.

Algorithm

  1. Step 1: Sort nums.
  2. Step 2: For each query [x, m], upper_bound finds index where num > m.
  3. Step 3: If index == 0, result is -1.
  4. Step 4: Else scan from 0 to index - 1 and compute max(x ^ num).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
9 sort(nums.begin(), nums.end());
10 vector<int> ans;
11
12 for (const auto& q : queries) {
13 int x = q[0], m = q[1];
14 auto it = upper_bound(nums.begin(), nums.end(), m);
15 if (it == nums.begin()) {
16 ans.push_back(-1);
17 } else {
18 int currMax = -1;
19 for (auto iter = nums.begin(); iter != it; ++iter) {
20 currMax = max(currMax, x ^ (*iter));
21 }
22 ans.push_back(currMax);
23 }
24 }
25 return ans;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> nums = {0, 1, 2, 3, 4};
32 vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};
33 auto res = sol.maximizeXor(nums, queries);
34 for (int v : res) cout << v << " ";
35 cout << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N log N + Q * (log N + K)) — Binary search takes O(log N) per query, but scanning up to K elements takes O(K) which can be O(N).
  • Space complexity: O(N) — Stores sorted array.

3. Offline Queries with Monotonic Binary Trie Insertion

Intuition

Store queries as tuples (m_i, x_i, original_index). Sort nums and sorted queries by m. Maintain a pointer ptr = 0 in nums. For each query, while ptr < nums.size() && nums[ptr] <= m, insert nums[ptr] into the Binary Trie. If Trie is empty, result is -1. Otherwise, greedily traverse the Trie to maximize XOR with x. Place result at original_index.

When to apply: Standard optimal solution required for full credit in hard interviews.

Algorithm

  1. Step 1: Sort nums in ascending order.
  2. Step 2: Package queries with original indices: [m, x, index]. Sort by m ascending.
  3. Step 3: Create root of Binary Trie and pointer ptr = 0.
  4. Step 4: For each query [m, x, original_idx]: while ptr < nums.size() && nums[ptr] <= m: insert nums[ptr++] into Trie.
  5. Step 5: If ptr == 0 (Trie is empty): ans[original_idx] = -1.
  6. Step 6: Else: query Trie for max XOR with x in 31 steps and assign ans[original_idx] = result.
  7. Step 7: Return ans.

Interactive Offline Query Processing Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: First query has m = 1
Visual state
Values and pointers at this exact step
tree
Root
(root)
num 0
0
num 1
1

Node order shown; add connections to display explicit tree edges.

m=1 threshold: 1
Check / comparison
nums[0]=0 <= 1, nums[1]=1 <= 1 inserted
Decision / next transition
Trie now contains 0 and 1.
Why this step matters

Step 1: First query has m = 1. Insert nums <= 1 (0 and 1) into Binary Trie. Pointer advances to index 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[2];
8 TrieNode() {
9 children[0] = nullptr;
10 children[1] = nullptr;
11 }
12};
13
14class Solution {
15 TrieNode* root;
16
17 void insert(int num) {
18 TrieNode* curr = root;
19 for (int i = 30; i >= 0; i--) {
20 int bit = (num >> i) & 1;
21 if (!curr->children[bit]) curr->children[bit] = new TrieNode();
22 curr = curr->children[bit];
23 }
24 }
25
26 int getMaxXor(int num) {
27 TrieNode* curr = root;
28 int maxVal = 0;
29 for (int i = 30; i >= 0; i--) {
30 int bit = (num >> i) & 1;
31 int oppBit = 1 - bit;
32 if (curr->children[oppBit]) {
33 maxVal |= (1 << i);
34 curr = curr->children[oppBit];
35 } else {
36 curr = curr->children[bit];
37 }
38 }
39 return maxVal;
40 }
41
42public:
43 vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
44 sort(nums.begin(), nums.end());
45
46 int qSize = queries.size();
47 vector<vector<int>> sortedQ(qSize);
48 for (int i = 0; i < qSize; i++) {
49 sortedQ[i] = {queries[i][1], queries[i][0], i}; // {m, x, original_idx}
50 }
51 sort(sortedQ.begin(), sortedQ.end());
52
53 root = new TrieNode();
54 vector<int> ans(qSize);
55 int ptr = 0, n = nums.size();
56
57 for (const auto& q : sortedQ) {
58 int m = q[0], x = q[1], originalIdx = q[2];
59 while (ptr < n && nums[ptr] <= m) {
60 insert(nums[ptr]);
61 ptr++;
62 }
63 if (ptr == 0) {
64 ans[originalIdx] = -1;
65 } else {
66 ans[originalIdx] = getMaxXor(x);
67 }
68 }
69 return ans;
70 }
71};
72
73int main() {
74 Solution sol;
75 vector<int> nums = {0, 1, 2, 3, 4};
76 vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};
77 auto res = sol.maximizeXor(nums, queries);
78 for (int v : res) cout << v << " ";
79 cout << endl;
80 return 0;
81}

Time & Space Complexity

  • Time complexity: O(N log N + Q log Q + (N + Q) * 32) — Sorting takes O(N log N + Q log Q). Each element is inserted into Trie once (31 steps), and each query takes 31 steps.
  • Space complexity: O(N * 32 + Q) — Trie nodes allocate at most 32 nodes per number. Q slots for answer array.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Filter and XOR per QueryO(Q * N)O(1)For each query [x, m], scan nums. If num <= m, compute x ^ num and track maximum. Return -1 if none.Scanning all numbers for every query.
2.Better — Binary Search Filter with Linear ScanO(N log N + Q * (log N + K))O(N)Sort nums. For query [x, m], find index of largest element <= m with binary search. Scan up to that index.Still scans large subsets of numbers.
3.Optimal — Offline Sorted Queries with Monotonic Binary TrieOptimalO(N log N + Q log Q + (N + Q) * 32)O(N * 32 + Q)Sort nums and sort queries by m. Use a pointer in nums to incrementally insert valid elements into a 32-bit Binary Trie. Query max XOR for x in O(32).None. Classical offline query optimization.

Common Pitfalls & Crucial Edge Cases

Attempting online querying without offline sorting

Re-inserting or filtering numbers per query degrades performance to O(Q * N).

Forgetting to restore original query indices

Writing answers in sorted order instead of the query's initial input order.

Not handling the empty Trie condition

If ptr == 0, attempting to query the Trie would cause null pointer exceptions.

Crucial Edge Cases to Validate:

  • m is smaller than the smallest number in nums — No valid elements exist; returns -1.
  • All queries have m >= max(nums) — All numbers inserted on first query; subsequent queries reuse the full Trie in O(32).
  • Array contains zero — Bitwise operations handle 0 seamlessly (31 zero bits).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the offline query paradigm: whenever queries have static inequality bounds, sorting queries by the bound converts the problem into monotonic insertions.
  2. Mention that each number in nums is visited and inserted exactly once, giving amortized O(1) insertions per query.
  3. Highlight the separation of concerns: query sorting handles the inequality constraint, while Binary Trie handles the XOR optimization.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why are the queries sorted by their threshold m?

2.If no numbers in nums are <= m_i, what should the query return?

Back to DSA Sheet