medium XOR Queries of a Subarray

Problem Statement

You are given an array arr containing integers greater than 0. Additionally, you are given the array of queries where queries[i] = [left_i, right_i].

For each query, compute the XOR of the elements in arr from index left_i to right_i (inclusive)

Return an array answer where answer[i] represents the result of the i^th query.

Examples

Example 1:

• Input: arr = [2, 4, 7, 3], queries = [[0, 1], [1, 3], [0, 2]]
• Expected Output: [6, 0, 1]
• Explanation:
  • For the first query [0, 1], XOR of elements from index 0 to 1: 2 XOR 4 = 6
  • For the second query [1, 3], XOR of elements from index 1 to 3: 4 XOR 7 XOR 3 = 0
  • For the third query [0, 2], XOR of elements from index 0 to 2: 2 XOR 4 XOR 7 = 1

Example 2:

• Input: arr = [5, 9, 12, 6], queries = [[2, 3], [0, 2], [1, 2]]
• Expected Output: [10, 0, 5]
• Explanation:
  • For the first query [2, 3], XOR of elements from index 2 to 3: 12 XOR 6 = 10
  • For the second query [0, 2], XOR of elements from index 0 to 2: 5 XOR 9 XOR 12 = 0
  • For the third query [1, 2], XOR of elements from index 1 to 2: 9 XOR 12 = 5

Example 3:

• Input: arr = [1, 3, 5, 7, 9], queries = [[1, 4], [0, 3], [2, 4]]
• Expected Output: [8, 0, 11]
• Explanation:
  • For the first query [1, 4], XOR of elements from index 1 to 4: 3 XOR 5 XOR 7 XOR 9 = 8
  • For the second query [0, 3], XOR of elements from index 0 to 3: 1 XOR 3 XOR 5 XOR 7 = 0
  • For the third query [2, 4], XOR of elements from index 2 to 4: 5 XOR 7 XOR 9 = 11

Constraints:

• 1 <= arr.length, queries.length <= 3 * 10⁴
• 1 <= arr[i] <= 10⁹
• queries[i].length == 2
• 0 <= left_i <= right_i < arr.length

Solution

To solve this problem, we can use Mo's Algorithm, which is a powerful technique used to answer multiple queries on an array in an efficient manner. The core idea is to sort the queries in a way that minimizes the amount of work needed to process them. We can do this by sorting based on the blocks of the query ranges and then processing each block while keeping track of the current XOR value. By moving the pointers to include or exclude elements in the current range, we can quickly compute the XOR for each query without recalculating from scratch.

This approach is effective because it reduces the time complexity compared to a naive approach where we would recompute the XOR for every query from scratch. By reusing the results from previous computations, we can answer each query in sub-linear time relative to the size of the array, making the algorithm scalable even for large inputs.

Step-by-Step Algorithm

1. Initialization:

   • Define a class Query that stores each query's left, right indices and its original index in the queries array. This is essential for keeping track of the order of queries after sorting.
   • Initialize blockSize as the square root of the length of arr.
   • Create an array qs[] to store the queries as Query objects, with each query’s left, right, and original index.

2. Sort Queries:

   • Sort the queries in qs[] based on:
     1. Block index calculated by left / blockSize.
     2. If two queries have the same block index, sort by right index.
   • This ordering minimizes the movement of currentLeft and currentRight pointers during query processing.

3. Initialize Pointers:

   • Set currentLeft to 0, currentRight to -1, and currentXor to 0.
   • These pointers track the current segment of arr[] being processed, and currentXor stores the XOR of this segment.

4. Process Each Query:

   • For each query in the sorted qs[]:
     1. Expand currentRight: While currentRight is less than query.right, move currentRight to the right, including new elements in the XOR calculation.
     2. Shrink currentRight: While currentRight is greater than query.right, move currentRight to the left, excluding elements from the XOR calculation.
     3. Expand currentLeft: While currentLeft is less than query.left, move currentLeft to the right, excluding elements from the XOR calculation.
     4. Shrink currentLeft: While currentLeft is greater than query.left, move currentLeft to the left, including new elements in the XOR calculation.
   • After adjusting currentLeft and currentRight, store the computed currentXor in answer[query.index].

5. Return the Results:

   • Once all queries are processed, return the answer[] array containing the results for each query.

Algorithm Walkthrough

Let’s walk through the algorithm with arr = [2, 4, 7, 3] and queries = [[0, 1], [1, 3], [0, 2]].

Step 1: Initialization

• queries = [[0, 1], [1, 3], [0, 2]]
• blockSize = 2 (since sqrt(4) = 2)
• answer[] = [0, 0, 0]

Step 2: Create Query objects

• qs[0] = Query(0, 1, 0) → corresponds to the first query.
• qs[1] = Query(1, 3, 1) → corresponds to the second query.
• qs[2] = Query(0, 2, 2) → corresponds to the third query.

Step 3: Sort the queries (qs[] array)

• Here, blockSize = 2. All queries belong to the first block. The sorted Queries are:
  • qs[0] = Query(0, 1, 0)
  • qs[1] = Query(0, 2, 2)
  • qs[2] = Query(1, 3, 1)

Step 4: Initialize pointers and currentXor

• currentLeft = 0
• currentRight = -1
• currentXor = 0

Step 5: Process the first query (Query(0, 1, 0))

• Expand currentRight to 1:
  • currentRight = 0, currentXor = 0 XOR arr[0] = 0 XOR 2 = 2
  • currentRight = 1, currentXor = 2 XOR arr[1] = 2 XOR 4 = 6
• No need to move currentLeft as it's already 0.
• Store result:
  • answer[0] = 6

Step 6: Process the second query (Query(0, 2, 2))

• Expand currentRight to 2:
  • currentRight = 2, currentXor = 6 XOR arr[2] = 6 XOR 7 = 1
• No need to move currentLeft as it's already 0.
• Store result:
  • answer[2] = 1

Step 7: Process the third query (Query(1, 3, 1))

• Expand currentRight to 3:
  • currentRight = 3, currentXor = 1 XOR arr[3] = 1 XOR 3 = 2
• Move currentLeft to 1:
  • currentXor = 2 XOR arr[0] = 2 XOR 2 = 0
• Store result:
  • answer[1] = 0

Final Output:

• answer[] = [6, 0, 1]

Code

import java.util.Arrays;

class Query {

  int left, right, index;

  Query(int l, int r, int i) {
    left = l;
    right = r;
    index = i;
  }
}

class Solution {

  public int[] xorQueries(int[] arr, int[][] queries) {
    int n = arr.length;
    int q = queries.length;
    int blockSize = (int) Math.sqrt(n); // Size of each block for Mo's algorithm
    int[] answer = new int[q];

    // Create an array of Query objects to hold the queries with their indices
    Query[] qs = new Query[q];
    for (int i = 0; i < q; i++) {
      qs[i] = new Query(queries[i][0], queries[i][1], i);
    }

    // Sort the queries according to the block and then by the right index
    Arrays.sort(qs, (a, b) -> {
      int blockA = a.left / blockSize;
      int blockB = b.left / blockSize;
      if (blockA != blockB) return blockA - blockB; // Sort by block
      return a.right - b.right; // Sort by right index if in the same block
    });

    int currentLeft = 0,
      currentRight = -1,
      currentXor = 0; // Initialize pointers and current XOR

    // Process each query in the sorted order
    for (Query query : qs) {
      // Expand the right boundary to include new elements in the XOR calculation
      while (currentRight < query.right) {
        currentRight++;
        currentXor ^= arr[currentRight];
      }
      // Shrink the right boundary to exclude elements from the XOR calculation
      while (currentRight > query.right) {
        currentXor ^= arr[currentRight];
        currentRight--;
      }
      // Expand the left boundary to exclude elements from the XOR calculation
      while (currentLeft < query.left) {
        currentXor ^= arr[currentLeft];
        currentLeft++;
      }
      // Shrink the left boundary to include new elements in the XOR calculation
      while (currentLeft > query.left) {
        currentLeft--;
        currentXor ^= arr[currentLeft];
      }

      answer[query.index] = currentXor;
    }

    return answer;
  }

  // Main method to test the xorQueries method with provided examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] arr1 = { 2, 4, 7, 3 };
    int[][] queries1 = { { 0, 1 }, { 1, 3 }, { 0, 2 } };
    int[] result1 = solution.xorQueries(arr1, queries1);
    System.out.println("Example 1 Output: " + Arrays.toString(result1)); // Expected Output: [6, 0, 1]

    // Example 2
    int[] arr2 = { 5, 9, 12, 6 };
    int[][] queries2 = { { 2, 3 }, { 0, 2 }, { 1, 2 } };
    int[] result2 = solution.xorQueries(arr2, queries2);
    System.out.println("Example 2 Output: " + Arrays.toString(result2)); // Expected Output: [10, 0, 5]

    // Example 3
    int[] arr3 = { 1, 3, 5, 7, 9 };
    int[][] queries3 = { { 1, 4 }, { 0, 3 }, { 2, 4 } };
    int[] result3 = solution.xorQueries(arr3, queries3);
    System.out.println("Example 3 Output: " + Arrays.toString(result3)); // Expected Output: [8, 0, 11]
  }
}

Complexity Analysis

Time Complexity

The overall time complexity is , according to Mo's algorithm.

Space Complexity

• Space for Results: Storing the results for each query takes space.
• Auxiliary Space: The array and auxiliary data structures require space.

Overall Space Complexity: