Given an array of integers arr.
We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).
Let's define a and b as follows:
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]Note that ^ denotes the bitwise-xor operation.
Return the number of triplets (i, j and k) Where a == b.
Example 1:
Input: arr = [2,3,1,6,7] Output: 4 Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)
Example 2:
Input: arr = [1,1,1,1,1] Output: 10
Constraints:
1 <= arr.length <= 3001 <= arr[i] <= 108Problem Overview: Given an integer array arr, count triplets (i, j, k) where 0 ≤ i < j ≤ k < n and the XOR of arr[i..j-1] equals the XOR of arr[j..k]. The task reduces to identifying segments where two adjacent subarrays share the same XOR value.
Approach 1: Utilize Prefix XOR (O(n2) time, O(n) space)
Compute a prefix XOR array where px[i] stores the XOR of elements from index 0 to i-1. Using the XOR identity a ^ a = 0, the condition arr[i..j-1] == arr[j..k] becomes px[i] == px[k+1]. Iterate over all pairs (i, k) and when the prefix XOR values match, every index between them can serve as a valid split point j. Each match contributes k - i triplets. This approach directly leverages properties of prefix sum-style preprocessing with XOR operations and is easy to implement but requires a quadratic scan.
Approach 2: Optimized Prefix XOR Count (O(n) time, O(n) space)
Track how often each prefix XOR value appears while scanning the array once. Maintain two hash maps: one for frequency of each prefix XOR and another for the total index sum where that XOR occurred. When the current prefix XOR repeats, it means earlier positions can form valid segments with the current index. The number of new triplets depends on how many times that XOR appeared and the distance between indices. Each step performs constant-time hash lookups, turning the quadratic search into a linear pass. This technique combines hash table counting with XOR prefix properties from bit manipulation.
Recommended for interviews: The optimized prefix XOR counting approach is what most interviewers expect. The quadratic prefix XOR version shows that you understand the mathematical reduction px[i] == px[k+1]. The linear hash‑map solution demonstrates deeper algorithmic insight and reduces the complexity to O(n), which is the optimal bound for scanning the array.
To find the number of triplets, we can utilize prefix XOR which makes checking if two subarrays have equal XOR efficient. For any indices i, j, k in the array, if the XOR from i to j-1 equals the XOR from j to k, we have a valid triplet. Using prefix XOR allows us to calculate this in constant time.
We compute the prefix XOR of the array where prefix[i] is the XOR from the start of the array to index i. For each pair of indices (i, k), if (prefix[i-1] == prefix[k]), then for all j where i <= j <= k, (i, j, k) will form a valid triplet.
In this Python solution, we use a prefix array to store the prefix XOR of the elements. We iterate over all possible pairs (i, k) and check if the XOR from the start to i-1 equals the XOR from the start to k. For every match, we then count the valid j indices that form a triplet.
Python
JavaScript
Time Complexity: O(n^2), where n is the length of the array, as we are using two nested loops.
Space Complexity: O(n), due to the storage of the prefix array.
This approach optimizes the first one by reducing redundant checks and efficiently calculating the number of valid triplet indices.
As we calculate the prefix XOR, we maintain a hashmap (or dictionary) which helps in counting valid j values directly, reducing the nested loop complexity by using suffix array observations.
In the Java solution, we use hashmaps to store the frequency and counts of the prefix XORs. This allows us to calculate the number of valid j indices without needing to iterate exhaustively, leveraging hash lookups instead.
Time Complexity: O(n), where n is the array length due to the optimization using hashmaps that distill the double loop.
Space Complexity: O(n), primarily due to hashmap storage.
According to the problem description, to find triplets (i, j, k) that satisfy a = b, which means s = a \oplus b = 0, we only need to enumerate the left endpoint i, and then calculate the prefix XOR sum s of the interval [i, k] with k as the right endpoint. If s = 0, then for any j \in [i + 1, k], the condition a = b is satisfied, meaning (i, j, k) is a valid triplet. There are k - i such triplets, which we can add to our answer.
After the enumeration is complete, we return the answer.
The time complexity is O(n^2), where n is the length of the array arr. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Utilize Prefix XOR | Time Complexity: O(n^2), where n is the length of the array, as we are using two nested loops. |
| Approach 2: Optimized Prefix XOR Count | Time Complexity: O(n), where n is the array length due to the optimization using hashmaps that distill the double loop. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix XOR Pair Enumeration | O(n^2) | O(n) | Useful for understanding the XOR property and during initial reasoning in interviews |
| Optimized Prefix XOR with Hash Counting | O(n) | O(n) | Best general solution; handles large arrays efficiently with constant‑time hash lookups |
Count Triplets That Can Form Two Arrays of Equal XOR - Leetcode 1442 - Python • NeetCodeIO • 10,848 views views
Watch 9 more video solutions →Practice Count Triplets That Can Form Two Arrays of Equal XOR with our built-in code editor and test cases.
Practice on FleetCode