Range XOR Queries with Subarray Reversals

Range XOR Queries with Subarray Reversals - Problem

You are given an integer array nums of length n and a 2D integer array queries of length q, where each query is one of the following three types:

Update: queries[i] = [1, index, value] - Set nums[index] = value.

Range XOR Query: queries[i] = [2, left, right] - Compute the bitwise XOR of all elements in the subarray nums[left...right], and record this result.

Reverse Subarray: queries[i] = [3, left, right] - Reverse the subarray nums[left...right] in place.

Return an array of the results of all range XOR queries in the order they were encountered.

Input & Output

Example 1 — Basic Mixed Operations

$ Input: nums = [1,3,4,8], queries = [[2,0,1],[1,1,5],[2,0,1],[3,0,3],[2,0,3]]

› Output: [2,4,6]

💡 Note: Query [2,0,1]: XOR of nums[0..1] = 1⊕3 = 2. Query [1,1,5]: Update nums[1] = 5. Query [2,0,1]: XOR of nums[0..1] = 1⊕5 = 4. Query [3,0,3]: Reverse nums[0..3] → [8,4,5,1]. Query [2,0,3]: XOR of nums[0..3] = 8⊕4⊕5⊕1 = 6.

Example 2 — Only XOR Queries

$ Input: nums = [2,3,4], queries = [[2,0,2],[2,1,2],[2,0,1]]

› Output: [5,7,1]

💡 Note: Query [2,0,2]: XOR of nums[0..2] = 2⊕3⊕4 = 5. Query [2,1,2]: XOR of nums[1..2] = 3⊕4 = 7. Query [2,0,1]: XOR of nums[0..1] = 2⊕3 = 1.

Example 3 — Update and Reverse

$ Input: nums = [5,6], queries = [[1,0,2],[3,0,1],[2,0,1]]

› Output: [4]

💡 Note: Query [1,0,2]: Update nums[0] = 2, so nums = [2,6]. Query [3,0,1]: Reverse nums[0..1] → [6,2]. Query [2,0,1]: XOR of nums[0..1] = 6⊕2 = 4.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁶
For update queries: 0 ≤ index < nums.length, 0 ≤ value ≤ 10⁶
For range queries: 0 ≤ left ≤ right < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and queries of three types

Process

Handle updates, XOR queries, and reversals

Output

Return results of all XOR queries

Key Takeaway

🎯 Key Insight: Process queries sequentially since XOR properties are preserved through array modifications

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to process queries sequentially since XOR operations and array modifications don't require complex data structures for this problem. The brute force approach handles all three operation types (update, XOR range query, reverse subarray) directly on the array. Best approach is sequential processing with helper functions for better organization. Time: O(q × n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Helper Functions	O(q × n)	O(1)	Use separate helper functions for each operation type with minor optimizations
Brute Force Sequential Processing	O(q × n)	O(1)	Process each query directly by modifying the array and computing XOR ranges when needed

Optimized with Helper Functions — Algorithm Steps

Create helper functions for each operation
Process queries using appropriate helper
Optimize reverse with two-pointer technique
Use bit manipulation properties for XOR

Visualization

Tap to expand

Step-by-Step Walkthrough

Helper Functions

Separate functions for each operation type

Operation Dispatch

Call appropriate helper based on query type

Result Collection

Efficiently collect XOR query results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void updateElement(int* arr, int index, int value) {
    arr[index] = value;
}

int xorRange(int* arr, int left, int right) {
    int result = 0;
    for (int i = left; i <= right; i++) {
        result ^= arr[i];
    }
    return result;
}

void reverseSubarray(int* arr, int left, int right) {
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

int* solution(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    int resultIndex = 0;
    
    for (int i = 0; i < queriesSize; i++) {
        int queryType = queries[i][0];
        
        if (queryType == 1) {  // Update
            updateElement(nums, queries[i][1], queries[i][2]);
        } else if (queryType == 2) {  // Range XOR Query
            int xorResult = xorRange(nums, queries[i][1], queries[i][2]);
            result[resultIndex++] = xorResult;
        } else if (queryType == 3) {  // Reverse Subarray
            reverseSubarray(nums, queries[i][1], queries[i][2]);
        }
    }
    
    *returnSize = resultIndex;
    return result;
}

int main() {
    int nums[] = {1, 3, 4, 8};
    int numsSize = 4;
    
    int query1[] = {2, 0, 1};
    int query2[] = {1, 1, 5};
    int query3[] = {2, 0, 1};
    int query4[] = {3, 0, 3};
    int query5[] = {2, 0, 3};
    
    int* queries[] = {query1, query2, query3, query4, query5};
    int queriesSize = 5;
    int queriesColSize[] = {3, 3, 3, 3, 3};
    
    int returnSize;
    int* result = solution(nums, numsSize, queries, queriesSize, queriesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

Same as brute force - each query may require O(n) operations for XOR or reverse

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for helper function variables

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Helper Functions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler