Maximum XOR Score Subarray Queries
HardPrompt
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:
- Simultaneously replace
a[i]witha[i] XOR a[i + 1]for all indicesiexcept the last one. - Remove the last element of
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 == 2queries[i] = [li, ri]0 <= li <= ri <= n - 1
Approaches
4 approaches with complexity analysis and trade-offs.
This is the most straightforward and naive approach. For each query, we generate every possible subarray within the given range [l, r]. For each of these subarrays, we compute its XOR score and keep track of the maximum score encountered. The XOR score calculation is done based on its definition involving bitwise operations related to binomial coefficients modulo 2.
Algorithm
- For each query
[l, r]in thequeriesarray:- Initialize a variable
max_scoreto 0. - Iterate through all possible start indices
ifromltor.- Iterate through all possible end indices
jfromitor.- This defines a subarray
nums[i..j]. - Calculate the XOR score of this subarray.
- To calculate the score of a subarray of length
len, letm = len - 1. - The score is the XOR sum of
nums[i+k]for allkfrom0tomsuch that(m & k) == k.
- To calculate the score of a subarray of length
- Update
max_score = max(max_score, current_subarray_score).
- This defines a subarray
- Iterate through all possible end indices
- After all subarrays are checked, the
max_scoreis the answer for the query[l, r].
- Initialize a variable
Walkthrough
The brute-force method directly translates the problem statement into code. It involves three nested loops for each query. The outer two loops iterate through all possible start (i) and end (j) points of subarrays within the query's range [l, r]. The innermost loop (or a helper function) calculates the XOR score for the subarray nums[i..j].
The score of a subarray a of length len is the XOR sum of its elements a[k] where the binary representation of k is a 'submask' of the binary representation of len - 1. This can be computed by iterating from k = 0 to len - 1 and checking the condition ((len - 1) & k) == k.
class Solution { private int calculateScore(int[] nums, int start, int end) { int len = end - start + 1; if (len == 0) return 0; int m = len - 1; int score = 0; for (int k = 0; k <= m; k++) { if ((m & k) == k) { score ^= nums[start + k]; } } return score; } public int[] maxSubarrayXORScore(int[] nums, int[][] queries) { int q = queries.length; int[] ans = new int[q]; for (int k = 0; k < q; k++) { int l = queries[k][0]; int r = queries[k][1]; int maxScore = 0; for (int i = l; i <= r; i++) { for (int j = i; j <= r; j++) { maxScore = Math.max(maxScore, calculateScore(nums, i, j)); } } ans[k] = maxScore; } return ans; }}Complexity
Time
O(q * n^3). For each of the `q` queries, we iterate through `O(n^2)` subarrays. Calculating the score for each subarray of length `k` takes `O(k)` time. In the worst case, `k` can be up to `n`, leading to the cubic complexity per query.
Space
O(1), as it only uses a few variables to store intermediate results, not counting the space for the output array.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space.
Cons
Extremely inefficient due to its high time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
We can optimize the score calculation by observing a dynamic programming structure. The score of an array [a_0, ..., a_k] is the same as the score of the transformed array [a_0^a_1, ..., a_{k-1}^a_k]. This allows us to pre-compute the scores of all O(n^2) subarrays in O(n^2) time. After pre-computation, we answer each query by iterating through the relevant pre-computed scores in the DP table.
Algorithm
- Pre-computation:
- Create a 2D DP table
Tof sizen x n, whereT[d][i]will store the XOR score of the subarraynums[i..i+d]. - Initialize the base cases:
T[0][i] = nums[i]for alli(scores of subarrays of length 1). - Fill the rest of the table using the recurrence:
T[d][i] = T[d-1][i] ^ T[d-1][i+1]. This takesO(n^2)time.
- Create a 2D DP table
- Query Processing:
- For each query
[l, r]:- Initialize
max_score = 0. - Iterate
ifromltorandjfromitor. - Look up the pre-computed score
T[j-i][i]. - Update
max_score = max(max_score, T[j-i][i]).
- Initialize
- Store
max_scoreas the answer.
- For each query
Walkthrough
This approach is based on a key recurrence relation for the XOR score. Let T[d][i] be the score of the subarray starting at i with length d+1 (i.e., nums[i..i+d]).
- The base cases are subarrays of length 1:
T[0][i] = nums[i]. - For a subarray of length
d+1,nums[i..i+d], its score is equivalent to the score of the array[nums[i]^nums[i+1], nums[i+1]^nums[i+2], ..., nums[i+d-1]^nums[i+d]]. This transformed array starts at indexi(in a conceptual transformed array) and has lengthd. Its score is thusT[d-1][i]based on the previous level of computation. This gives the recurrenceT[d][i] = T[d-1][i] ^ T[d-1][i+1].
We can build this n x n table T in O(n^2) time. Once T is populated, for each query [l, r], we simply iterate through all subarrays nums[i..j] within this range and look up their scores T[j-i][i] to find the maximum.
class Solution { public int[] maxSubarrayXORScore(int[] nums, int[][] queries) { int n = nums.length; int[][] T = new int[n][n]; for (int i = 0; i < n; i++) { T[0][i] = nums[i]; } for (int d = 1; d < n; d++) { for (int i = 0; i <= n - 1 - d; i++) { T[d][i] = T[d - 1][i] ^ T[d - 1][i + 1]; } } int q = queries.length; int[] ans = new int[q]; for (int k = 0; k < q; k++) { int l = queries[k][0]; int r = queries[k][1]; int maxScore = 0; for (int i = l; i <= r; i++) { for (int j = i; j <= r; j++) { maxScore = Math.max(maxScore, T[j - i][i]); } } ans[k] = maxScore; } return ans; }}Complexity
Time
O(n^2 + q * n^2). The pre-computation takes `O(n^2)`. Each of the `q` queries then takes `O(n^2)` to check all relevant entries in the pre-computed table.
Space
O(n^2) to store the DP table `T`.
Trade-offs
Pros
Efficiently pre-computes all subarray scores.
Much faster than the pure brute-force approach.
Cons
The query processing part is still very slow, making the overall approach inefficient for a large number of queries.
Requires significant
O(n^2)space for the DP table.
This approach improves upon the previous one by optimizing the query phase. After pre-computing all subarray scores in the T table, we recognize that for a given query [l, r], we are essentially performing a 2D range query on T. We can break this down. For each starting position i in the query range, we need the maximum score of subarrays starting at i and ending within the range. This is a Range Maximum Query (RMQ) on a column of our T table. By pre-building a Sparse Table for each column, we can answer these column-wise queries efficiently.
Algorithm
- Pre-computation Step 1 (DP Table):
- Compute the
T[d][i]table storing all subarray scores inO(n^2)time, as in the previous approach.
- Compute the
- Pre-computation Step 2 (Sparse Tables):
- For each column
iof theTtable, build a Sparse Table data structure. This allows forO(1)Range Maximum Queries (RMQ) on that column. - Building sparse tables for all
ncolumns takes a total ofO(n^2 log n)time.
- For each column
- Query Processing:
- For each query
[l, r]:- The problem is to find
max_{i=l..r} (max_{d=0..r-i} T[d][i]). - Iterate
ifromltor. - For each
i, use the pre-built sparse table for columnito find the maximum value in the range ofdfrom0tor-i. This query takesO(1). - Keep track of the overall maximum.
- The problem is to find
- For each query
Walkthrough
The query for [l, r] asks for max_{l <= i <= j <= r} T[j-i][i]. This can be rewritten as max_{i=l..r} (max_{j=i..r} T[j-i][i]). By substituting d = j-i, the inner maximum becomes max_{d=0..r-i} T[d][i], which is a prefix maximum query on column i of the T table.
To accelerate this, we pre-process each column of T to handle RMQ. A Sparse Table is an ideal data structure for this, offering O(k log k) build time for a column of size k and O(1) query time.
- DP Table
T: Compute inO(n^2).T[d][i]is the score ofnums[i..i+d]. - Sparse Tables: For each column
ifrom0ton-1, create a sparse table on the array[T[0][i], T[1][i], ..., T[n-1-i][i]]. Total build time isO(n^2 log n). - Queries: For a query
[l, r], we iterateifromltor. In each iteration, we query the sparse table for columnito findmax_{d=0..r-i} T[d][i]inO(1). The total time for a query becomesO(r-l+1), which isO(n)in the worst case.
This reduces the overall complexity, making it feasible for larger inputs than the previous approach.
Complexity
Time
O(n^2 log n + q * n). `O(n^2 log n)` for pre-computation (DP table + sparse tables) and `O(n)` for each of the `q` queries.
Space
O(n^2 log n). The `T` table takes `O(n^2)` space, but the sparse tables for all columns dominate, requiring `O(n^2 log n)` space.
Trade-offs
Pros
Much faster query time compared to the simple DP approach.
Makes the problem tractable for the given constraints, though it might be on the edge of the time limit.
Cons
The
O(q*n)query part can still be a bottleneck if bothqandnare large.High space complexity due to storing
nsparse tables.
This is the most efficient approach, optimizing the query time to a constant O(1). It builds upon the DP foundation by performing further pre-computation. After calculating all scores, we compute column-wise prefix maximums. The crucial insight is that a query [l, r] corresponds to finding the maximum over a set of values that all lie on a single anti-diagonal of this new prefix-max table. By pre-building sparse tables for each anti-diagonal, we can answer any query in constant time.
Algorithm
- Step 1: DP Table
T- Compute
T[d][i](score ofnums[i..i+d]) inO(n^2)time.
- Compute
- Step 2: Column-Prefix-Max Table
CMax- Create a new table
CMax[d][i] = max_{k=0..d} T[k][i]. - This can be computed in
O(n^2)using the recurrenceCMax[d][i] = max(CMax[d-1][i], T[d][i]).
- Create a new table
- Step 3: Sparse Tables on Diagonals
- The query for
[l, r]simplifies tomax_{i=l..r} CMax[r-i][i]. - All points
(d, i) = (r-i, i)lie on the anti-diagonal whered+i = r. - For each anti-diagonal
k(from0ton-1), create an array of its elements fromCMaxand build a Sparse Table on it. - This pre-computation takes
O(n^2 log n)time and space.
- The query for
- Step 4: Query Processing
- A query
[l, r]now translates to an RMQ on ther-th anti-diagonal's sparse table over the index range[l, r]. - This takes
O(1)time.
- A query
Walkthrough
This approach refines the query process to achieve O(1) time per query.
- First, compute the
T[d][i]table of all subarray scores inO(n^2). - Next, we transform the query problem. A query
[l, r]seeksmax_{i=l..r} (max_{d=0..r-i} T[d][i]). We can pre-calculate the inner maximum. LetCMax[d][i] = max_{k=0..d} T[k][i]. This table can be computed inO(n^2)time. The query then becomes findingmax_{i=l..r} CMax[r-i][i]. - The key observation is that for a fixed query
[l, r], all the accessed entriesCMax[r-i][i]have indices(d, i)whered+i = (r-i)+i = r. This means they all lie on the anti-diagonalk=rof theCMaxtable. - Therefore, we can pre-process the anti-diagonals. For each anti-diagonal
k(from0ton-1, sinceris at mostn-1), we construct a sparse table. Thei-th element on diagonalkisCMax[k-i][i]. Building these sparse tables takesO(n^2 log n)time. - With this structure, a query
[l, r]is answered by a singleO(1)lookup in the sparse table for anti-diagonalr, querying the range of indices[l, r].
// Conceptual structure; requires a SparseTable helper class.class Solution { public int[] maxSubarrayXORScore(int[] nums, int[][] queries) { int n = nums.length; // 1. Compute T[d][i] int[][] T = new int[n][n]; for (int i = 0; i < n; i++) T[0][i] = nums[i]; for (int d = 1; d < n; d++) { for (int i = 0; i <= n - 1 - d; i++) { T[d][i] = T[d - 1][i] ^ T[d - 1][i + 1]; } } // 2. Compute CMax[d][i] int[][] CMax = new int[n][n]; for (int i = 0; i < n; i++) { CMax[0][i] = T[0][i]; for (int d = 1; d < n - i; d++) { CMax[d][i] = Math.max(CMax[d - 1][i], T[d][i]); } } // 3. Build Sparse Tables for diagonals of CMax SparseTable[] diagonalST = new SparseTable[n]; for (int k = 0; k < n; k++) { // k = r, the diagonal index int[] diagonal = new int[k + 1]; for (int i = 0; i <= k; i++) { // i is the index on the diagonal diagonal[i] = CMax[k - i][i]; } diagonalST[k] = new SparseTable(diagonal); } // 4. Process queries in O(1) each int q = queries.length; int[] ans = new int[q]; for (int i = 0; i < q; i++) { int l = queries[i][0]; int r = queries[i][1]; ans[i] = diagonalST[r].query(l, r); } return ans; }}// Assume SparseTable class is implemented for RMQ in O(1)Complexity
Time
O(n^2 log n + q). `O(n^2)` for the `T` and `CMax` tables, `O(n^2 log n)` for building all sparse tables, and `O(1)` for each of the `q` queries.
Space
O(n^2 log n). The dominant factor is the space required to store the sparse tables for all `n` relevant anti-diagonals.
Trade-offs
Pros
Extremely fast
O(1)query time, making it ideal for a large number of queries.The overall solution is very efficient and comfortably passes the time limits.
Cons
The implementation is complex, requiring multiple layers of data structures (DP table, prefix-max table, and sparse tables).
Requires a large amount of memory,
O(n^2 log n).
Solutions
Solution
class Solution {public int[] maximumSubarrayXor(int[] nums, int[][] queries) { int n = nums.length; int[][] f = new int[n][n]; int[][] g = new int[n][n]; for (int i = n - 1; i >= 0; --i) { f[i][i] = nums[i]; g[i][i] = nums[i]; for (int j = i + 1; j < n; ++j) { f[i][j] = f[i][j - 1] ^ f[i + 1][j]; g[i][j] = Math.max(f[i][j], Math.max(g[i][j - 1], g[i + 1][j])); } } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int l = queries[i][0], r = queries[i][1]; ans[i] = g[l][r]; } return ans; }}class Solution {public: vector<int> maximumSubarrayXor(vector<int> &nums, vector<vector<int>> &queries) { int n = nums.size(); vector<vector<int>> f(n, vector<int>(n)); vector<vector<int>> g(n, vector<int>(n)); for (int i = n - 1; i >= 0; --i) { f[i][i] = nums[i]; g[i][i] = nums[i]; for (int j = i + 1; j < n; ++j) { f[i][j] = f[i][j - 1] ^ f[i + 1][j]; g[i][j] = max({f[i][j], g[i][j - 1], g[i + 1][j]}); } } vector<int> ans; for (const auto &q : queries) { int l = q[0], r = q[1]; ans.push_back(g[l][r]); } return ans; }};class Solution: def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]: n = len(nums) f = [[0] * n for _ in range(n)] g = [[0] * n for _ in range(n)] for i in range(n - 1, - 1, - 1): f[i][i] = g[i][i] = nums[i] for j in range(i + 1, n): f[i][j] = f[i][j - 1] ^ f[i + 1][j] g[i][j] = max(f[i][j], g[i][j - 1], g[i + 1][j]) return [g[l][r] for l, r in queries]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.