Construct List using XOR Queries

Time: O(qlogq)

Space: O(q)

Problem Overview

Every type-1 query applies XOR to all elements currently in the list.

Intuition

Every type-1 query applies XOR to all elements currently in the list. Since XOR is associative and commutative, you can flip the perspective: process queries from right to left while maintaining a cumulative xor (xr) of all type-1 values you have seen. When you encounter a type-0 insertion of x, the value that x ends up with is x XOR xr (because xr represents the XOR operations that will be applied to it later). Finally, include the initial element 0 XOR xr and sort the results.

Algorithm

1Initialise xr = 0 and an empty results list.
2Traverse queries from the last query down to the first:
3If query type is 1 with value x, update xr ^= x.
4If query type is 0 with value x, append (x ^ xr) to results.
5After the loop, append xr to results to represent the initial element 0 XOR xr.
6Sort results in increasing order and return it.

Example Walkthrough

Input: q = 5, queries = [[0,6],[0,3],[0,2],[1,4],[1,5]]

1. Start xr = 0, results = [].
2. Process {1,5} → xr = 0 ^ 5 = 5.
3. Process {1,4} → xr = 5 ^ 4 = 1.
4. Process {0,2} → add 2 ^ 1 = 3.
5. Process {0,3} → add 3 ^ 1 = 2.
6. Process {0,6} → add 6 ^ 1 = 7.
7. Add initial 0 ^ xr → add 1.
8. Sort: [3,2,7,1] → [1,2,3,7].

Output: 1 2 3 7

Common Pitfalls

• Traverse from right to left so you can accumulate XOR operations instead of updating every element forward.
• Include the initial element 0 (add xr at the end).
• Sort the final list before returning.

Construct List using XOR Queries.java

Java


// Approach: Type-1 queries apply XOR to every existing element, so the final value of an inserted x depends on
// the XOR of all type-1 query values that appear after the insertion.
// Process queries from right to left while keeping cumulativeXor = XOR of all seen type-1 values.
// When you see a type-0 (insert x), add x XOR cumulativeXor to the answer list.
// After all queries, the initial element 0 becomes 0 XOR cumulativeXor = cumulativeXor; add it too.
// Sort the collected list in increasing order.
// Time: O(qlogq) Space: O(q)
import java.util.*;

class Solution {

    public ArrayList<Integer> constructList(int[][] queries) {
        ArrayList<Integer> arr = new ArrayList<>();
        // Stores cumulative XOR effect of all type-1 queries seen so far
        int sum = 0, q = queries.length;
        // Process queries from end to start
        for (int i = q - 1; i >= 0; i--) {
            // Type 0: Insert x
            if (queries[i][0] == 0) {
                // Apply all future XOR operations to x
                arr.add(queries[i][1] ^ sum);
            } else {
                // Accumulate XOR operations
                sum ^= queries[i][1];
            }
        }
        // Initial element 0 becomes (0 ^ sum) so 0^sum=sum
        arr.add(sum);
        // Return sorted result
        Collections.sort(arr);
        return arr;
    }
}

Was this solution helpful?