Skip to main content
Talentd

Maximum XOR With an Element From Array - Solution & Explanation

HardArrayBit ManipulationTrie16 min readAsked at: Google
Practice this problem

Problem Statement

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [xi, mi].

The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi. In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi. If all elements in nums are larger than mi, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.

 

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array nums and queries [xi, mi]. For each query, choose a number from nums that is <= mi and maximize xi XOR num. If no valid number exists, return -1. The challenge is handling many queries efficiently while respecting the upper bound constraint.

Approach 1: Sorting and Binary Search (O(n log n + q log n + kq) time, O(1) extra space)

Start by sorting nums. For each query, use binary search to find the largest index where nums[i] <= mi. This gives the subset of values eligible for that query. Iterate through that prefix and compute xi ^ nums[j] for each candidate while tracking the maximum. The binary search reduces the filtering step from O(n) to O(log n), but the XOR scan can still reach O(n) in the worst case.

This approach is straightforward and works when constraints are small or when you want a quick baseline implementation. However, repeated scans across queries make it inefficient when both nums and queries are large.

Approach 2: Trie Data Structure (O((n + q) * 32) time, O(n * 32) space)

The optimal approach uses a bitwise Trie. Each node represents a bit (0 or 1). Insert numbers from nums bit by bit from the most significant bit (31) down to the least significant bit (0). While querying, greedily move toward the opposite bit to maximize the XOR value.

The constraint num <= mi is handled using an offline processing trick. Sort nums and sort queries by mi. As you process queries in increasing order of mi, insert all numbers from nums that satisfy the limit into the Trie. Then compute the maximum XOR for xi using the current Trie state. Each insertion and query takes about 32 steps because integers are 32-bit.

This technique combines ideas from array preprocessing, bit manipulation, and Trie traversal. The offline sorting ensures each number is inserted exactly once, keeping the algorithm efficient.

Recommended for interviews: The Trie-based solution is the expected answer for hard interview settings. It demonstrates understanding of bitwise optimization and offline query processing. A simpler sorted-array scan can show initial reasoning, but the Trie approach proves you can design scalable solutions under tight constraints.

Approach 1: Approach 1: Sorting and Binary Search

Sort the array and for each query, use binary search to find the largest element <= m. Then compute the XOR for eligible numbers and find the maximum result.

This code first sorts the nums array and then performs a binary search to find the largest valid index for each query. The maximum XOR is calculated by iterating over valid elements only.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n + q log n), where n is the number of elements in nums and q is the number of queries.

Space Complexity: O(1) excluding the space required for the output.

Try this approach in the editor β†’

Approach 2: Approach 2: Trie Data Structure

Build a Trie data structure to efficiently find the number that gives the maximum XOR with a given number. This is useful for queries constrained by a maximum value since it supports parts of operations in logarithmic time.

This code constructs a Trie to store the binary representation of numbers. For each query, it traverses the Trie to maximize the XOR. The query checks if adding a set bit (1) keeps the result below the xor threshold.

Code

C

C

Complexity

Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers.

Space Complexity: O(n * MAX_BIT), needed for Trie structure.

Try this approach in the editor β†’

Approach 3: Offline Query + Binary Trie

From the problem description, we know that each query is independent and the result of the query is irrelevant to the order of elements in nums. Therefore, we consider sorting all queries in ascending order of m_i, and also sorting nums in ascending order.

Next, we use a binary trie to maintain the elements in nums. We use a pointer j to record the current elements in the trie, initially j=0. For each query [x_i, m_i], we continuously insert elements from nums into the trie until nums[j] > m_i. At this point, we can query all elements not exceeding m_i in the trie, and we take the XOR value of the element with the maximum XOR value with x_i as the answer.

The time complexity is O(m times log m + n times (log n + log M)), and the space complexity is O(n times log M). Where m and n are the lengths of the arrays nums and queries respectively, and M is the maximum value in the array nums. In this problem, M \le 10^9.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Binary Search

Time Complexity: O(n log n + q log n), where n is the number of elements in nums and q is the number of queries.

Space Complexity: O(1) excluding the space required for the output.

Approach 2: Trie Data Structure

Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers.

Space Complexity: O(n * MAX_BIT), needed for Trie structure.

Offline Query + Binary Trieβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Binary Search with ScanO(n log n + q log n + nq)O(1)Simple baseline approach when constraints are small
Offline Queries + Bitwise TrieO((n + q) * 32 + n log n + q log q)O(n * 32)Optimal solution for large inputs and interview scenarios

Video Solution

θŠ±θŠ±ι…± LeetCode 1707. Maximum XOR With an Element From Array - εˆ·ι’˜ζ‰Ύε·₯作 EP377 β€’ Hua Hua β€’ 2,615 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Maximum XOR With an Element From Array easy or hard?
The problem is classified as Hard because it combines multiple concepts: offline query processing, bit manipulation, and Trie data structures. A naive scan is easy to write, but designing the optimal Trie solution requires deeper algorithmic insight.
Maximum XOR With an Element From Array Python/Java solution
Implementations in Python, Java, C++, and JavaScript follow the same pattern: sort nums, sort queries with indices, insert valid numbers into a Trie, and compute the maximum XOR for each query. Each query takes about 32 steps in the Trie.
How to solve Maximum XOR With an Element From Array in O(n)?
Strict O(n) is not achievable because queries must be processed and sorted by the limit value. The closest practical complexity is O((n + q) * 32) using a bitwise Trie with offline query sorting, which behaves close to linear for typical constraints.
What is the best approach for Maximum XOR With an Element From Array?
The best approach uses an offline query strategy combined with a bitwise Trie. Sort both the array and queries by the limit value m, insert eligible numbers into the Trie, and compute the maximum XOR greedily for each query. This keeps the complexity around O((n + q) * 32) after sorting.
Is Maximum XOR With an Element From Array asked at Google/Amazon/Meta?
Variants of maximum XOR and bitwise Trie problems frequently appear in interviews at companies like Google, Amazon, and Meta. Interviewers use them to test understanding of bit manipulation, prefix structures, and efficient query processing.
What data structure is used in Maximum XOR With an Element From Array?
The key data structure is a bitwise Trie (binary prefix tree). Each level represents a bit position, allowing greedy traversal toward the opposite bit to maximize XOR during queries.
What is the time complexity of Maximum XOR With an Element From Array?
The optimal Trie-based solution runs in O((n + q) * 32) time for Trie operations plus O(n log n + q log q) for sorting. Since integers have at most 32 bits, each insert and query takes constant time relative to input size.

Ready to solve this problem?

Practice Maximum XOR With an Element From Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Genetic Difference Query

Next

Maximum Strong Pair XOR I