You are given an array nums of n integers, and a 2D integer array queries of size q, where queries[i] = [li, ri].
For each query, you must find the maximum XOR score of any subarray of nums[li..ri].
The XOR score of an array a is found by repeatedly applying the following operations on a so that only one element remains, that is the score:
a[i] with a[i] XOR a[i + 1] for all indices i except the last one.a.Return an array answer of size q where answer[i] is the answer to query i.
Example 1:
Input: nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]
Output: [12,60,60]
Explanation:
In the first query, nums[0..2] has 6 subarrays [2], [8], [4], [2, 8], [8, 4], and [2, 8, 4] each with a respective XOR score of 2, 8, 4, 10, 12, and 6. The answer for the query is 12, the largest of all XOR scores.
In the second query, the subarray of nums[1..4] with the largest XOR score is nums[1..4] with a score of 60.
In the third query, the subarray of nums[0..5] with the largest XOR score is nums[1..4] with a score of 60.
Example 2:
Input: nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]
Output: [7,14,11,14,5]
Explanation:
| Index | nums[li..ri] | Maximum XOR Score Subarray | Maximum Subarray XOR Score |
|---|---|---|---|
| 0 | [0, 7, 3, 2] | [7] | 7 |
| 1 | [7, 3, 2, 8, 5] | [7, 3, 2, 8] | 14 |
| 2 | [3, 2, 8] | [3, 2, 8] | 11 |
| 3 | [3, 2, 8, 5, 1] | [2, 8, 5, 1] | 14 |
| 4 | [5, 1] | [5] | 5 |
Constraints:
1 <= n == nums.length <= 20000 <= nums[i] <= 231 - 11 <= q == queries.length <= 105queries[i].length == 2 queries[i] = [li, ri]0 <= li <= ri <= n - 1Problem Overview: You are given an integer array and multiple queries. Each query asks for the maximum XOR score obtainable from any subarray inside the specified range. A naive scan per query is far too slow, so the solution relies on precomputing XOR relationships and reusing them efficiently.
Approach 1: Prefix XOR + Dynamic Programming (O(n^2) preprocessing, O(1) per query)
The key observation is that the XOR of any subarray nums[l..r] can be computed using a prefix XOR array: xor = prefix[r+1] ^ prefix[l]. Once you can compute subarray XOR instantly, you can build a dynamic programming table where dp[i][j] stores the maximum XOR value of any subarray within the range [i, j]. Expand ranges gradually: either extend the previous interval or compute the XOR of the entire segment using prefix values. Each query then becomes a constant-time lookup. This approach is straightforward and leverages concepts from Array processing and Dynamic Programming. The tradeoff is memory and preprocessing time of O(n^2), which is acceptable only when constraints are moderate.
Approach 2: Trie-Based Optimization (O((n + q) log A) time, O(n log A) space)
A more scalable solution uses a binary trie to maximize XOR values. Store prefix XOR values in a trie where each level represents a bit. When processing prefixes, you attempt to find another prefix that maximizes the XOR result. For query ranges, maintain structures (or persistent versions) that represent prefixes up to a certain index so you can restrict candidates to the query boundaries. Each lookup walks the trie greedily, always choosing the opposite bit when possible to maximize the XOR value. This technique relies heavily on Array traversal and bitwise operations, and is a common trick in maximum XOR problems using a Trie. Because trie depth is limited by the integer bit-length (typically 31–32), each operation runs in logarithmic time relative to the value range.
Recommended for interviews: Start by explaining the prefix XOR property and how it enables constant-time subarray XOR calculation. Building a DP table demonstrates clear understanding of range-based optimization. For stronger performance discussions, introduce the trie-based method and explain how greedy bit selection maximizes XOR values. Interviewers typically expect the prefix XOR insight first, followed by the trie optimization for handling larger inputs efficiently.
This approach uses a prefix XOR array to calculate the XOR of any subarray efficiently. The maximum XOR of any subarray nums[l..r] can be computed using prefixXOR[r+1] XOR prefixXOR[l]. By storing all prefix XORs encountered so far, we can efficiently find the maximum XOR for each query by iterating through possible subarrays.
This Python code defines a function find_max_xor that calculates the maximum XOR of any subarray using prefix XOR and a set to track seen prefix XORs. The main function max_xor_queries iterates over each query, extracts the subarray, and uses the helper function to get the maximum XOR score for that subarray.
Python
JavaScript
Time Complexity: O(q * n)
Space Complexity: O(n)
This approach uses a Trie data structure to efficiently compute the maximum XOR of subarrays. For each prefix, insert its representation into the Trie and use this structure to find the maximum XOR by traversing the Trie.
This Java code solution uses a Trie to check for maximum XOR subarray more efficiently. We insert the prefix XOR into the Trie and use it to check possible maximum XOR values by diverging at each bit level of the Trie when possible.
Time Complexity: O(n * 32 + q)
Space Complexity: O(n * 32)
We define f[i][j] to represent the XOR value of nums[i..j]. According to the problem description, we can derive the state transition equation:
$
f[i][j] = f[i][j-1] \oplus f[i+1][j]
where \oplus denotes the XOR operation.
We further define g[i][j] to represent the maximum value of f[i][j]. The state transition equation is:
g[i][j] = max(f[i][j], g[i][j-1], g[i+1][j])
Finally, we traverse the query array. For each query [l, r], we add g[l][r] to the answer array.
The time complexity is O(n^2 + m), and the space complexity is O(n^2). Here, n and m are the lengths of the arrays nums and queries$, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix XOR Array Technique | Time Complexity: O(q * n) |
| Trie-Based Optimization | Time Complexity: O(n * 32 + q) |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix XOR + DP Table | O(n^2) preprocessing, O(1) per query | O(n^2) | When constraints allow quadratic preprocessing and you want extremely fast query answers |
| Binary Trie Optimization | O((n + q) log A) | O(n log A) | Large arrays or many queries where quadratic preprocessing is too expensive |
3277. Maximum XOR Score Subarray Queries | Weekly Leetcode 413 • codingMohan • 1,279 views views
Watch 5 more video solutions →Practice Maximum XOR Score Subarray Queries with our built-in code editor and test cases.
Practice on FleetCode