Subarray XOR Queries
Solve this ProblemMedium20–25 min
Topics
Bit ManipulationPrefix XOR
Companies
AmazonMicrosoftAdobe
You're given an array
nums and a batch of range queries, each one a pair [l, r]. For every query, return the XOR of every value in nums from index l through r inclusive — one answer per query, in the order the queries were given.
Answering each query by walking its range works, but ranges across different queries overlap constantly. A single pass that builds a running XOR up to every index first turns each query into a lookup: XOR the running total up to r with the running total up to l − 1, and everything outside [l, r] cancels itself out completely.
Test Case 1:
Input:nums = [5, 2, 7, 1, 9], queries = [[0, 2], [1, 4], [2, 2]]
Output:[0, 13, 7]
Explanation:5^2^7=0, 2^7^1^9=13, and the single-index range [2,2] is just nums[2]=7.
Test Case 2:
Input:nums = [0, 1, 2, 3, 4], queries = [[0, 4]]
Output:[4]
Explanation:One query spanning the whole array: 0^1^2^3^4=4.
Test Case 3:
Input:nums = [6], queries = [[0, 0]]
Output:[6]
Explanation:A single-element array queried at its only valid range.
Constraints
- ◆
1 ≤ nums.length ≤ 3 × 10⁴ - ◆
1 ≤ queries.length ≤ 3 × 10⁴ - ◆
0 ≤ l ≤ r ≤ nums.length − 1 for every query - ◆
0 ≤ nums[i] ≤ 10⁵
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — XOR Each Subarray Directly
BruteFor every query, walk from l to r and fold each value into a running XOR. Simple and correct, but ranges across different queries overlap constantly, and this approach redoes that shared work from scratch every single time.
Time
O(q × n)Space
O(1) extraJava
1class Solution {
2 public int[] subarrayXorQueries(int[] nums, int[][] queries) {
3 int[] answers = new int[queries.length];
4 for (int i = 0; i < queries.length; i++) {
5 int l = queries[i][0];
6 int r = queries[i][1];
7 int result = 0;
8 for (int j = l; j <= r; j++) {
9 result ^= nums[j];
10 }
11 answers[i] = result;
12 }
13 return answers;
14 }
15}Optimal — Prefix XOR
OptimalBuild a running XOR up to every index once, up front. Once that prefix is available, the XOR of any subarray [l, r] falls out of just two prefix values — the one up to r and the one up to l − 1 — since combining the same prefix against itself would cancel it, leaving exactly the range in between.
Time
O(n + q)Space
O(n)Java
1class Solution {
2 public int[] subarrayXorQueries(int[] nums, int[][] queries) {
3 int n = nums.length;
4 int[] prefix = new int[n + 1];
5 for (int i = 0; i < n; i++) {
6 prefix[i + 1] = prefix[i] ^ nums[i];
7 }
8 int[] answers = new int[queries.length];
9 for (int i = 0; i < queries.length; i++) {
10 int l = queries[i][0];
11 int r = queries[i][1];
12 answers[i] = prefix[r + 1] ^ prefix[l];
13 }
14 return answers;
15 }
16}