Maximum XOR Score Subarray Queries solution and explanation
Google
5 more videos on this problem
3277. Maximum XOR Score Subarray Queries | Weekly Leetcode 413codingMohan · 38:03 · 1K views
3277. Maximum XOR Score Subarray Queries | LeetCode weekly contest 413Amit Dhyani · 33:05 · 620 views
3277. Maximum XOR Score Subarray Queries (Leetcode Hard)Programming Live with Larry · 1:01:23 · 401 views
3277. Maximum XOR Score Subarray Queries | leetcode weekly contest 413CodingHelp · 20:11 · 128 views
3277. Maximum XOR Score Subarray Queries in Hindi | Leetcode Weekly Contest 413 | Geekstocode | DPGeekstocode · 45:55 · 80 views
3277 maximum xor score subarray queriesCodePen · 1:21 · 4 views
The problem
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
Approach overview
Problem 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 1: Prefix XOR Array Technique
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.
def max_xor_queries(nums, queries):
def find_max_xor(arr):
max_xor = 0
prefix_xor = 0
prefix_set = set([0])
for num in arr:
prefix_xor ^= num
max_xor = max(max_xor, prefix_xor ^ prefix ^ number for prefix in prefix_set)
prefix_set.add(prefix_xor)
return max_xor
results = []
for l, r in queries:
results.append(find_max_xor(nums[l:r+1]))
return results
# Example usage
nums = [2, 8, 4, 32, 16, 1]
queries = [[0, 2], [1, 4], [0, 5]]
print(max_xor_queries(nums, queries)) # Output: [12, 60, 60]function maxXorQueries(nums, queries) {
function findMaxXOR(arr) {
let prefixXOR = 0;
let maxXOR = 0;
let seen = new Set([0]);
for (const num of arr) {
prefixXOR ^= num;
for (const prefix of seen) {
maxXOR = Math.max(maxXOR, prefixXOR ^ prefix);
}
seen.add(prefixXOR);
}
return maxXOR;
}
const results = [];
for (const [l, r] of queries) {
results.push(findMaxXOR(nums.slice(l, r + 1)));
}
return results;
}
// Example usage
let nums = [2, 8, 4, 32, 16, 1];
let queries = [[0, 2], [1, 4], [0, 5]];
console.log(maxXorQueries(nums, queries)); // Output: [12, 60, 60]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.
Time Complexity: O(q * n)
Space Complexity: O(n)
Approach 2: Trie-Based Optimization
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.
import java.util.*;
class MaxXorWithTrie {
static class TrieNode {
TrieNode[] children = new TrieNode[2];
}
public int maxXOR(int[] nums, int[][] queries) {
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int l = queries[i][0], r = queries[i][1];
result[i] = findMaxXOR(Arrays.copyOfRange(nums, l, r + 1));
}
return result;
}
private int findMaxXOR(int[] nums) {
TrieNode root = new TrieNode();
int max_xor = 0;
int prefix_xor = 0;
insertTrie(root, prefix_xor);
for (int num : nums) {
prefix_xor ^= num;
insertTrie(root, prefix_xor);
max_xor = Math.max(max_xor, findMaximumXOR(root, prefix_xor));
}
return max_xor;
}
private void insertTrie(TrieNode root, int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
private int findMaximumXOR(TrieNode root, int num) {
TrieNode node = root;
int max_xor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[1 - bit] != null) {
max_xor |= (1 << i);
node = node.children[1 - bit];
} else {
node = node.children[bit];
}
}
return max_xor;
}
public static void main(String[] args) {
MaxXorWithTrie solution = new MaxXorWithTrie();
int[] nums = {2, 8, 4, 32, 16, 1};
int[][] queries = {{0, 2}, {1, 4}, {0, 5}};
int[] result = solution.maxXOR(nums, queries);
System.out.println(Arrays.toString(result)); // Output: [12, 60, 60]
}
}using System;
using System.Linq;
public class MaxXORSubarray {
public class TrieNode {
public TrieNode[] children = new TrieNode[2];
}
public int[] MaxXORQueries(int[] nums, int[][] queries) {
int[] results = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int l = queries[i][0], r = queries[i][1];
results[i] = FindMaxXOR(nums, l, r);
}
return results;
}
private int FindMaxXOR(int[] nums, int l, int r) {
var root = new TrieNode();
int max_xor = 0, prefix_xor = 0;
InsertTrie(root, prefix_xor);
for (int i = l; i <= r; i++) {
prefix_xor ^= nums[i];
InsertTrie(root, prefix_xor);
max_xor = Math.Max(max_xor, FindMaximumXOR(root, prefix_xor));
}
return max_xor;
}
private void InsertTrie(TrieNode root, int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
}
}
private int FindMaximumXOR(TrieNode root, int num) {
TrieNode curr = root;
int max_xor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[1 - bit] != null) {
max_xor |= (1 << i);
curr = curr.children[1 - bit];
} else {
curr = curr.children[bit];
}
}
return max_xor;
}
public static void Main(String[] args) {
var solution = new MaxXORSubarray();
int[] nums = {2, 8, 4, 32, 16, 1};
int[][] queries = new int[][] {new int[] {0, 2}, new int[] {1, 4}, new int[] {0, 5}};
int[] result = solution.MaxXORQueries(nums, queries);
Console.WriteLine(string.Join(", ", result)); // Output: 12, 60, 60
}
}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)
Approach 3: Dynamic Programming
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.
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;
}
};function maximumSubarrayXor(nums: number[], queries: number[][]): number[] {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
f[i][i] = nums[i];
g[i][i] = nums[i];
for (let 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]));
}
}
return queries.map(([l, r]) => g[l][r]);
}func maximumSubarrayXor(nums []int, queries [][]int) (ans []int) {
n := len(nums)
f := make([][]int, n)
g := make([][]int, n)
for i := 0; i < n; i++ {
f[i] = make([]int, n)
g[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
f[i][i] = nums[i]
g[i][i] = nums[i]
for j := i + 1; j < n; j++ {
f[i][j] = f[i][j-1] ^ f[i+1][j]
g[i][j] = max(f[i][j], max(g[i][j-1], g[i+1][j]))
}
}
for _, q := range queries {
l, r := q[0], q[1]
ans = append(ans, g[l][r])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix XOR Array Technique | Time Complexity: O(q * n) |
| Trie-Based Optimization | Time Complexity: O(n * 32 + q) |
| Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum XOR Score Subarray Queries easy or hard?
Maximum XOR Score Subarray Queries is categorized as a Hard problem because it combines multiple concepts: prefix XOR properties, dynamic programming over ranges, and trie-based bit manipulation for optimization.
Maximum XOR Score Subarray Queries Python/Java solution
Python implementations typically use the prefix XOR and dynamic programming approach due to its simplicity. Java solutions often implement the optimized version with a binary trie for better performance on large inputs. Both approaches rely on fast XOR operations and prefix preprocessing.
How to solve Maximum XOR Score Subarray Queries in O(n log A)?
Build a prefix XOR array and insert prefix values into a binary trie. For each prefix, query the trie to find another prefix that maximizes the XOR value by greedily selecting opposite bits. Because the trie depth equals the number of bits in the integers, each insert and query takes O(log A) time.
What is the best approach for Maximum XOR Score Subarray Queries?
The most practical approach combines prefix XOR with advanced structures such as a binary trie. Prefix XOR allows constant-time calculation of any subarray XOR, while the trie efficiently finds the maximum XOR pairing among prefixes. This reduces query processing to roughly O(log A) time where A is the maximum integer value.
Is Maximum XOR Score Subarray Queries asked at Google/Amazon/Meta?
XOR maximization problems and trie-based bit manipulation questions frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as maximum XOR pair, maximum XOR subarray, and range XOR queries test understanding of prefix XOR and bitwise tries.
What data structure is used in Maximum XOR Score Subarray Queries?
The main structures are a prefix XOR array and a binary trie. The prefix array enables constant-time subarray XOR computation, while the trie helps efficiently search for values that maximize the XOR result during query processing.
What is the time complexity of Maximum XOR Score Subarray Queries?
The prefix XOR with dynamic programming approach requires O(n^2) preprocessing and answers each query in O(1). A trie-based optimization improves scalability with about O((n + q) log A) time, where A represents the bit-length of numbers stored in the trie.