Maximum XOR Score Subarray Queries

Hard
1661.

Maximum XOR Score Subarray Queries

Maximum XOR Score Subarray Queries is a hard coding problem on arrays and dynamic programming, asked in Amazon interviews.

You are given an array nums of n non-negative integers and a 2D array queries, where queries[i] = [l_i, r_i].

The XOR score of an array a is found by repeating the following until only one element is left: replace every a[i] with a[i] XOR a[i + 1] for all indices except the last, then remove the last element. The single remaining element is the score.

For each query, return the maximum XOR score over all subarrays of nums[l_i..r_i] (inclusive). Return an array answer where answer[i] is the answer to the i-th query.

Example 1

Input
nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]
Output
[12,60,60]
Explanation
In [2,8,4] the subarray [8,4] scores 8 XOR 4 = 12. In [8,4,32,16] the subarray [4,32,16] scores (4^32)^(32^16) = 60, and nothing in the whole array beats it.

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]

Example 3

Input
nums = [5], queries = [[0,0]]
Output
[5]
Explanation
A one-element array scores its only element.

Constraints

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 2^31 - 1
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= l_i <= r_i <= n - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var maximumSubarrayXor = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum XOR Score Subarray Queries — Problem & Solution

Maximum XOR Score Subarray Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum XOR Score Subarray Queries is a hard coding problem on arrays and dynamic programming, asked in Amazon interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of n non-negative integers and a 2D array queries, where queries[i] = [l_i, r_i].

The XOR score of an array a is found by repeating the following until only one element is left: replace every a[i] with a[i] XOR a[i + 1] for all indices except the last, then remove the last element. The single remaining element is the score.

For each query, return the maximum XOR score over all subarrays of nums[l_i..r_i] (inclusive). Return an array answer where answer[i] is the answer to the i-th query.

Example 1

Input: nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]
Output: [12,60,60]
Explanation: In [2,8,4] the subarray [8,4] scores 8 XOR 4 = 12. In [8,4,32,16] the subarray [4,32,16] scores (4^32)^(32^16) = 60, and nothing in the whole array beats it.

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]

Example 3

Input: nums = [5], queries = [[0,0]]
Output: [5]
Explanation: A one-element array scores its only element.

Constraints

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 2^31 - 1
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= l_i <= r_i <= n - 1

Hints for Maximum XOR Score Subarray Queries

  1. Hint 1

    Write out the score of nums[i..j] after its first step: it is the score of an array of length j - i built from neighbouring XORs. Can you relate it to shorter subarrays of nums itself?

  2. Hint 2

    The score satisfies score(i, j) = score(i, j - 1) XOR score(i + 1, j) — the reduction is linear, like Pascal's triangle.

  3. Hint 3

    Fill score for all O(n^2) pairs, then best(i, j) = max(score(i, j), best(i, j - 1), best(i + 1, j)) answers every query in O(1).

How to solve Maximum XOR Score Subarray Queries

The XOR reduction is a Pascal-triangle process: the score of nums[i..j] equals score(i, j - 1) XOR score(i + 1, j). That gives every subarray's score in O(n^2), and a second table of the best score inside each range answers the queries by lookup.

Approach

  1. Iterate i from n - 1 down to 0 and j from i up to n - 1.
  2. Set score[i][i] = best[i][i] = nums[i]; for j > i, score[i][j] = score[i][j - 1] XOR score[i + 1][j].
  3. Set best[i][j] = max(score[i][j], best[i][j - 1], best[i + 1][j]) — every subarray of [i, j] is either the whole range or lies inside one of the two shorter ranges.
  4. For each query [l, r], answer best[l][r].

Why it works

After one step the array nums[i..j] becomes d[k] = nums[k] XOR nums[k + 1] for k in i..j-1, and the score is linear in its input over XOR. By induction the score of nums[i..j] is the XOR of the elements whose binomial coefficient C(j - i, k - i) is odd; Pascal's rule C(m, t) = C(m - 1, t) + C(m - 1, t - 1) turns that into score(i, j - 1) XOR score(i + 1, j).

Complexity

  • Time — O(n^2 + q)
  • Space — O(n^2)

Pitfalls

  • Simulating the reduction per subarray is O(n^3) per query range — far too slow for 2000 elements.
  • best must include the scores of all inner subarrays, not only the ones starting at l or ending at r.

Reference solution

Python

from typing import List

def maximumSubarrayXor(nums: List[int], queries: List[List[int]]) -> List[int]:
    n = len(nums)
    score = [[0] * n for _ in range(n)]
    best = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        score[i][i] = best[i][i] = nums[i]
        for j in range(i + 1, n):
            score[i][j] = score[i][j - 1] ^ score[i + 1][j]
            best[i][j] = max(score[i][j], best[i][j - 1], best[i + 1][j])
    return [best[l][r] for l, r in queries]

Java

public static int[] maximumSubarrayXor(int[] nums, int[][] queries) {
    int n = nums.length;
    int[][] score = new int[n][n];
    int[][] best = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        score[i][i] = nums[i];
        best[i][i] = nums[i];
        for (int j = i + 1; j < n; j++) {
            score[i][j] = score[i][j - 1] ^ score[i + 1][j];
            best[i][j] = Math.max(score[i][j], Math.max(best[i][j - 1], best[i + 1][j]));
        }
    }
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) out[q] = best[queries[q][0]][queries[q][1]];
    return out;
}

C++

vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size();
    vector<vector<int>> score(n, vector<int>(n, 0)), best(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        score[i][i] = best[i][i] = nums[i];
        for (int j = i + 1; j < n; j++) {
            score[i][j] = score[i][j - 1] ^ score[i + 1][j];
            best[i][j] = max(score[i][j], max(best[i][j - 1], best[i + 1][j]));
        }
    }
    vector<int> out;
    for (auto& q : queries) out.push_back(best[q[0]][q[1]]);
    return out;
}

JavaScript

var maximumSubarrayXor = function(nums, queries) {
    var n = nums.length;
    var score = [], best = [];
    for (var a = 0; a < n; a++) { score.push(new Array(n).fill(0)); best.push(new Array(n).fill(0)); }
    for (var i = n - 1; i >= 0; i--) {
        score[i][i] = nums[i];
        best[i][i] = nums[i];
        for (var j = i + 1; j < n; j++) {
            score[i][j] = score[i][j - 1] ^ score[i + 1][j];
            best[i][j] = Math.max(score[i][j], best[i][j - 1], best[i + 1][j]);
        }
    }
    var out = [];
    for (var q = 0; q < queries.length; q++) out.push(best[queries[q][0]][queries[q][1]]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming