LeetCode 3277 - Maximum XOR Score Subarray Queries

The problem gives us an integer array nums and several range queries. For each query [li, ri], we must examine every possible subarray fully contained inside nums[li..ri] and return the maximum XOR score among them.

leetcodehardarraydynamic-programming

LeetCode Problem 3277

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us an integer array nums and several range queries. For each query [li, ri], we must examine every possible subarray fully contained inside nums[li..ri] and return the maximum XOR score among them.

The unusual part of the problem is the definition of the XOR score. Instead of simply XORing all elements directly, the array is repeatedly transformed:

  • Every element becomes a[i] XOR a[i + 1]
  • The last element is removed
  • This process continues until only one number remains

That final number is the score of the array.

At first glance, this transformation may look complicated because it repeatedly shrinks the array. However, there is a strong mathematical structure hidden inside it, which allows dynamic programming to solve the problem efficiently.

The input constraints are important:

  • n <= 2000
  • q <= 100000

The array is relatively small, but the number of queries is very large. This strongly suggests that we should preprocess information about all subarrays once, then answer each query in constant time.

A naive per-query solution would be far too slow because there can be up to one hundred thousand queries.

Several edge cases are important:

  • A query may contain only one element, in which case the answer is simply that element.
  • All numbers may be zero.
  • The maximum score might come from a very small subarray, not necessarily the whole query range.
  • The XOR score is not the same as the normal XOR of the subarray, so using prefix XOR directly does not work.

Approaches

Brute Force

The brute-force solution considers every query independently.

For a query [l, r], we enumerate every subarray inside that range. For each subarray, we simulate the repeated XOR transformation until one element remains, then track the maximum score found.

If a subarray has length k, simulating the process directly takes O(k^2) time because we repeatedly rebuild smaller arrays.

There are O(n^2) subarrays inside a range, so this approach becomes extremely expensive.

Even with some optimization, the total complexity is far beyond acceptable limits for n = 2000 and q = 100000.

Key Insight

The crucial observation is that the XOR score of a subarray can be computed recursively.

Define:

score(l, r)

as the XOR score of subarray nums[l..r].

The transformation property leads to this recurrence:

score(l, r) = score(l, r - 1) XOR score(l + 1, r)

This works because one reduction step transforms the array into pairwise XORs, and the remaining process behaves recursively.

Once we can compute every subarray score using dynamic programming, we can build another DP table:

best(l, r)

which stores the maximum XOR score among all subarrays inside nums[l..r].

The recurrence becomes:

best(l, r) = max(
    score(l, r),
    best(l + 1, r),
    best(l, r - 1)
)

This preprocessing takes only O(n^2) time, after which every query is answered in O(1) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(q * n^4) O(1) Enumerates all subarrays and simulates reductions
Optimal O(n^2 + q) O(n^2) Dynamic programming precomputes all answers

Algorithm Walkthrough

  1. Create a 2D DP table called xor_score.

xor_score[l][r] will store the XOR score of subarray nums[l..r]. 2. Initialize all single-element subarrays.

A subarray of length 1 already has only one element, so:

xor_score[i][i] = nums[i]
  1. Fill the table by increasing subarray length.

For every subarray nums[l..r] with length greater than 1:

xor_score[l][r] =
    xor_score[l][r - 1] XOR xor_score[l + 1][r]

This recurrence follows directly from the repeated transformation process. 4. Create another DP table called best.

best[l][r] represents the maximum XOR score among every subarray contained inside nums[l..r]. 5. Initialize length-1 intervals.

best[i][i] = nums[i]
  1. Fill the best table by increasing interval length.

For each interval [l, r]:

best[l][r] = max(
    xor_score[l][r],
    best[l + 1][r],
    best[l][r - 1]
)

This works because every subarray inside [l, r] is either:

  • The whole interval itself
  • Fully inside [l + 1, r]
  • Fully inside [l, r - 1]
  1. Answer queries directly.

For each query [l, r], return:

best[l][r]

Why it works

The correctness comes from two recursive properties.

First, the XOR score recurrence exactly mirrors the shrinking XOR process. Each reduction step creates pairwise XORs, and recursively applying the same operation leads to:

score(l, r) = score(l, r - 1) XOR score(l + 1, r)

Second, every subarray inside [l, r] either excludes the left endpoint, excludes the right endpoint, or equals the entire interval. Therefore the maximum value must appear in one of those three cases, which makes the best recurrence complete and correct.

Python Solution

from typing import List

class Solution:
    def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)

        xor_score = [[0] * n for _ in range(n)]
        best = [[0] * n for _ in range(n)]

        for i in range(n):
            xor_score[i][i] = nums[i]
            best[i][i] = nums[i]

        for length in range(2, n + 1):
            for left in range(n - length + 1):
                right = left + length - 1

                xor_score[left][right] = (
                    xor_score[left][right - 1]
                    ^ xor_score[left + 1][right]
                )

                best[left][right] = max(
                    xor_score[left][right],
                    best[left + 1][right],
                    best[left][right - 1]
                )

        return [best[left][right] for left, right in queries]

The implementation closely follows the dynamic programming formulation.

The xor_score table stores the XOR score for every subarray. The diagonal is initialized with the original array values because a single element already represents its own score.

The nested loops process subarrays in increasing order of length. This ordering is essential because the recurrence depends on smaller intervals that must already be computed.

The best table stores the maximum score obtainable inside each interval. At every step, we compare:

  • The score of the whole interval
  • The best result excluding the left endpoint
  • The best result excluding the right endpoint

Finally, queries are answered in constant time by directly reading from best.

Go Solution

func maximumSubarrayXor(nums []int, queries [][]int) []int {
	n := len(nums)

	xorScore := make([][]int, n)
	best := make([][]int, n)

	for i := 0; i < n; i++ {
		xorScore[i] = make([]int, n)
		best[i] = make([]int, n)

		xorScore[i][i] = nums[i]
		best[i][i] = nums[i]
	}

	for length := 2; length <= n; length++ {
		for left := 0; left+length-1 < n; left++ {
			right := left + length - 1

			xorScore[left][right] =
				xorScore[left][right-1] ^
					xorScore[left+1][right]

			bestValue := xorScore[left][right]

			if best[left+1][right] > bestValue {
				bestValue = best[left+1][right]
			}

			if best[left][right-1] > bestValue {
				bestValue = best[left][right-1]
			}

			best[left][right] = bestValue
		}
	}

	answer := make([]int, len(queries))

	for i, query := range queries {
		left := query[0]
		right := query[1]

		answer[i] = best[left][right]
	}

	return answer
}

The Go implementation mirrors the Python version almost exactly.

Go uses explicit 2D slice allocation, while Python uses list comprehensions. Integer overflow is not a concern because Go's int type easily handles the given constraints. Query answering remains constant time because all preprocessing is completed beforehand.

Worked Examples

Example 1

Input:

nums = [2,8,4,32,16,1]
queries = [[0,2],[1,4],[0,5]]

Step 1: Build xor_score

Length 1:

Subarray Score
[2] 2
[8] 8
[4] 4
[32] 32
[16] 16
[1] 1

Length 2:

Subarray Computation Score
[2,8] 2 XOR 8 10
[8,4] 8 XOR 4 12
[4,32] 4 XOR 32 36
[32,16] 32 XOR 16 48
[16,1] 16 XOR 1 17

Length 3:

Subarray Computation Score
[2,8,4] 10 XOR 12 6
[8,4,32] 12 XOR 36 40
[4,32,16] 36 XOR 48 20
[32,16,1] 48 XOR 17 33

Continue similarly for larger lengths.

Step 2: Build best

For interval [0,2]:

best[0][2] =
max(
    xor_score[0][2] = 6,
    best[1][2] = 12,
    best[0][1] = 10
)
= 12

For interval [1,4]:

best[1][4] = 60

For interval [0,5]:

best[0][5] = 60

Final answers:

[12, 60, 60]

Example 2

Input:

nums = [0,7,3,2,8,5,1]
queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

Important interval calculations:

Interval Maximum Score
[0,3] 7
[1,5] 14
[2,4] 11
[2,6] 14
[5,6] 5

Final output:

[7,14,11,14,5]

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 + q) DP preprocessing takes O(n^2), queries are O(1) each
Space O(n^2) Two DP tables of size n × n

The dominant cost comes from filling the two dynamic programming tables. Since every interval [l, r] is processed once, the total preprocessing cost is quadratic. Query answering is constant time because all results are already stored.

Test Cases

sol = Solution()

# Example 1
assert sol.maximumSubarrayXor(
    [2,8,4,32,16,1],
    [[0,2],[1,4],[0,5]]
) == [12,60,60]  # provided example

# Example 2
assert sol.maximumSubarrayXor(
    [0,7,3,2,8,5,1],
    [[0,3],[1,5],[2,4],[2,6],[5,6]]
) == [7,14,11,14,5]  # provided example

# Single element array
assert sol.maximumSubarrayXor(
    [5],
    [[0,0]]
) == [5]  # smallest possible input

# All zeros
assert sol.maximumSubarrayXor(
    [0,0,0,0],
    [[0,3],[1,2]]
) == [0,0]  # XOR remains zero everywhere

# Two elements
assert sol.maximumSubarrayXor(
    [1,2],
    [[0,1],[0,0],[1,1]]
) == [3,1,2]  # simple pair testing

# Maximum comes from smaller subarray
assert sol.maximumSubarrayXor(
    [8,1,2],
    [[0,2]]
) == [11]  # best is subarray [8,1,2]

# Repeated values
assert sol.maximumSubarrayXor(
    [7,7,7,7],
    [[0,3]]
) == [7]  # repeated pattern

# Larger mixed values
assert sol.maximumSubarrayXor(
    [5,9,12,3,15],
    [[0,4],[1,3],[2,4]]
) == [15,15,15]  # stress different ranges

Test Summary

Test Why
Example 1 Verifies core correctness
Example 2 Verifies multiple overlapping queries
Single element Tests minimum boundary
All zeros Ensures XOR propagation works correctly
Two elements Tests smallest nontrivial subarrays
Smaller subarray optimal Ensures algorithm does not assume full interval is best
Repeated values Tests symmetric/repetitive patterns
Larger mixed values Exercises broader DP coverage

Edge Cases

A single-element query is the simplest edge case. Since the reduction process already starts with one element, no XOR operations occur. A buggy implementation might incorrectly apply transitions or access invalid indices. The DP initialization handles this correctly by setting both xor_score[i][i] and best[i][i] directly to nums[i].

Arrays containing only zeros are another important case. XOR operations on zero always remain zero, so every subarray score should also be zero. Some implementations accidentally introduce garbage values by failing to initialize DP tables properly. Since this solution explicitly initializes all base cases and uses only XOR operations on computed values, zero arrays work naturally.

Another subtle case occurs when the best answer comes from a smaller subarray rather than the full query interval. A naive optimization might incorrectly compute only the score of the whole interval. The best DP table avoids this mistake because it explicitly tracks the maximum among all contained subarrays, not just the interval itself.