Watch 6 video solutions for Maximum XOR Score Subarray Queries, a hard level problem involving Array, Dynamic Programming. This walkthrough by codingMohan has 1,279 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |