Maximum XOR Score Subarray Queries — Problem & Solution
Maximum XOR Score Subarray Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum XOR Score Subarray Queries is a hard coding problem on arrays and dynamic programming, asked in Amazon interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of n non-negative integers and a 2D array queries, where queries[i] = [l_i, r_i].
The XOR score of an array a is found by repeating the following until only one element is left: replace every a[i] with a[i] XOR a[i + 1] for all indices except the last, then remove the last element. The single remaining element is the score.
For each query, return the maximum XOR score over all subarrays of nums[l_i..r_i] (inclusive). Return an array answer where answer[i] is the answer to the i-th query.
Example 1
Input: nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]
Output: [12,60,60]
Explanation: In [2,8,4] the subarray [8,4] scores 8 XOR 4 = 12. In [8,4,32,16] the subarray [4,32,16] scores (4^32)^(32^16) = 60, and nothing in the whole array beats it.
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]
Example 3
Input: nums = [5], queries = [[0,0]]
Output: [5]
Explanation: A one-element array scores its only element.
Constraints
1 <= n == nums.length <= 20000 <= nums[i] <= 2^31 - 11 <= queries.length <= 10^5queries[i].length == 20 <= l_i <= r_i <= n - 1
Hints for Maximum XOR Score Subarray Queries
Hint 1
Write out the score of
nums[i..j]after its first step: it is the score of an array of lengthj - ibuilt from neighbouring XORs. Can you relate it to shorter subarrays ofnumsitself?Hint 2
The score satisfies
score(i, j) = score(i, j - 1) XOR score(i + 1, j)— the reduction is linear, like Pascal's triangle.Hint 3
Fill
scorefor allO(n^2)pairs, thenbest(i, j) = max(score(i, j), best(i, j - 1), best(i + 1, j))answers every query inO(1).
How to solve Maximum XOR Score Subarray Queries
The XOR reduction is a Pascal-triangle process: the score of nums[i..j] equals score(i, j - 1) XOR score(i + 1, j). That gives every subarray's score in O(n^2), and a second table of the best score inside each range answers the queries by lookup.
Approach
- Iterate
ifromn - 1down to 0 andjfromiup ton - 1. - Set
score[i][i] = best[i][i] = nums[i]; forj > i,score[i][j] = score[i][j - 1] XOR score[i + 1][j]. - Set
best[i][j] = max(score[i][j], best[i][j - 1], best[i + 1][j])— every subarray of[i, j]is either the whole range or lies inside one of the two shorter ranges. - For each query
[l, r], answerbest[l][r].
Why it works
After one step the array nums[i..j] becomes d[k] = nums[k] XOR nums[k + 1] for k in i..j-1, and the score is linear in its input over XOR. By induction the score of nums[i..j] is the XOR of the elements whose binomial coefficient C(j - i, k - i) is odd; Pascal's rule C(m, t) = C(m - 1, t) + C(m - 1, t - 1) turns that into score(i, j - 1) XOR score(i + 1, j).
Complexity
- Time —
O(n^2 + q) - Space —
O(n^2)
Pitfalls
- Simulating the reduction per subarray is
O(n^3)per query range — far too slow for 2000 elements. bestmust include the scores of all inner subarrays, not only the ones starting atlor ending atr.
Reference solution
Python
from typing import List
def maximumSubarrayXor(nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
score = [[0] * n for _ in range(n)]
best = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
score[i][i] = best[i][i] = nums[i]
for j in range(i + 1, n):
score[i][j] = score[i][j - 1] ^ score[i + 1][j]
best[i][j] = max(score[i][j], best[i][j - 1], best[i + 1][j])
return [best[l][r] for l, r in queries]Java
public static int[] maximumSubarrayXor(int[] nums, int[][] queries) {
int n = nums.length;
int[][] score = new int[n][n];
int[][] best = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
score[i][i] = nums[i];
best[i][i] = nums[i];
for (int j = i + 1; j < n; j++) {
score[i][j] = score[i][j - 1] ^ score[i + 1][j];
best[i][j] = Math.max(score[i][j], Math.max(best[i][j - 1], best[i + 1][j]));
}
}
int[] out = new int[queries.length];
for (int q = 0; q < queries.length; q++) out[q] = best[queries[q][0]][queries[q][1]];
return out;
}C++
vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<vector<int>> score(n, vector<int>(n, 0)), best(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
score[i][i] = best[i][i] = nums[i];
for (int j = i + 1; j < n; j++) {
score[i][j] = score[i][j - 1] ^ score[i + 1][j];
best[i][j] = max(score[i][j], max(best[i][j - 1], best[i + 1][j]));
}
}
vector<int> out;
for (auto& q : queries) out.push_back(best[q[0]][q[1]]);
return out;
}JavaScript
var maximumSubarrayXor = function(nums, queries) {
var n = nums.length;
var score = [], best = [];
for (var a = 0; a < n; a++) { score.push(new Array(n).fill(0)); best.push(new Array(n).fill(0)); }
for (var i = n - 1; i >= 0; i--) {
score[i][i] = nums[i];
best[i][i] = nums[i];
for (var j = i + 1; j < n; j++) {
score[i][j] = score[i][j - 1] ^ score[i + 1][j];
best[i][j] = Math.max(score[i][j], best[i][j - 1], best[i + 1][j]);
}
}
var out = [];
for (var q = 0; q < queries.length; q++) out.push(best[queries[q][0]][queries[q][1]]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming