3277. Maximum XOR Score Subarray Queries LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3277. Maximum XOR Score Subarray Queries LeetCode Solution with the best time and space complexity. The solution to Maximum XOR Score Subarray Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum XOR Score Subarray Queries solution in C++
Maximum XOR Score Subarray Queries solution in Java
Maximum XOR Score Subarray Queries solution in Python
Additional Resources

3277. Maximum XOR Score Subarray Queries LeetCode Solution image

Problem Statement of Maximum XOR Score Subarray Queries

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

3277. Maximum XOR Score Subarray Queries LeetCode Solution in C++

class Solution {
 public:
  vector<int> maximumSubarrayXor(vector<int>& nums,
                                 vector<vector<int>>& queries) {
    const int n = nums.size();
    vector<int> ans;
    // xors[i][j] := the XOR score of nums[i..j]
    vector<vector<int>> xors(n, vector<int>(n));
    // dp[i][j] := the maximum XOR score of nums[i..j]
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
      xors[i][i] = nums[i];
      dp[i][i] = nums[i];
    }

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        xors[i][j] = xors[i][j - 1] ^ xors[i + 1][j];
        dp[i][j] = max({xors[i][j], dp[i][j - 1], dp[i + 1][j]});
      }

    for (const vector<int>& query : queries) {
      const int l = query[0];
      const int r = query[1];
      ans.push_back(dp[l][r]);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3277. Maximum XOR Score Subarray Queries LeetCode Solution in Java

class Solution {
  public int[] maximumSubarrayXor(int[] nums, int[][] queries) {
    final int n = nums.length;
    int[] ans = new int[queries.length];
    // xors[i][j] := the XOR score of nums[i..j]
    int[][] xors = new int[n][n];
    // dp[i][j] := the maximum XOR score of nums[i..j]
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; ++i) {
      xors[i][i] = nums[i];
      dp[i][i] = nums[i];
    }

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        xors[i][j] = xors[i][j - 1] ^ xors[i + 1][j];
        dp[i][j] = Math.max(xors[i][j], Math.max(dp[i][j - 1], dp[i + 1][j]));
      }

    for (int i = 0; i < queries.length; ++i) {
      final int l = queries[i][0];
      final int r = queries[i][1];
      ans[i] = dp[l][r];
    }

    return ans;
  }
}
// code provided by PROGIEZ

3277. Maximum XOR Score Subarray Queries LeetCode Solution in Python

class Solution:
  def maximumSubarrayXor(
      self,
      nums: list[int],
      queries: list[list[int]]
  ) -> list[int]:
    n = len(nums)
    # xors[i][j] := the XOR score of nums[i..j]
    xors = [[0] * n for _ in range(n)]
    # dp[i][j] := the maximum XOR score of nums[i..j]
    dp = [[0] * n for _ in range(n)]

    for i, num in enumerate(nums):
      xors[i][i] = num
      dp[i][i] = num

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        xors[i][j] = xors[i][j - 1] ^ xors[i + 1][j]
        dp[i][j] = max(xors[i][j], dp[i][j - 1], dp[i + 1][j])

    return [dp[l][r] for l, r in queries]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents