Skip to main content
Talentd

Maximum XOR Score Subarray Queries - Solution & Explanation

HardArrayDynamic Programming13 min readAsked at: Google
Practice this problem

Problem Statement

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] with a[i] XOR a[i + 1] for all indices i except 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 <= 2000
  • 0 <= nums[i] <= 231 - 1
  • 1 <= q == queries.length <= 105
  • queries[i].length == 2
  • queries[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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(q * n)
Space Complexity: O(n)

Try this approach in the editor →

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.

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.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n * 32 + q)
Space Complexity: O(n * 32)

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix XOR Array Technique

Time Complexity: O(q * n)
Space Complexity: O(n)

Trie-Based Optimization

Time Complexity: O(n * 32 + q)
Space Complexity: O(n * 32)

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix XOR + DP TableO(n^2) preprocessing, O(1) per queryO(n^2)When constraints allow quadratic preprocessing and you want extremely fast query answers
Binary Trie OptimizationO((n + q) log A)O(n log A)Large arrays or many queries where quadratic preprocessing is too expensive

Video Solution

3277. Maximum XOR Score Subarray Queries | Weekly Leetcode 413 • codingMohan • 1,319 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Maximum XOR Score Subarray Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make the XOR of All Segments Equal to Zero