Given an integer array nums, return the length of the longest subarray that has a bitwise XOR of zero and contains an equal number of even and odd numbers. If no such subarray exists, return 0.
Example 1:
Input: nums = [3,1,3,2,0]
Output: 4
Explanation:
The subarray [1, 3, 2, 0] has bitwise XOR 1 XOR 3 XOR 2 XOR 0 = 0 and contains 2 even and 2 odd numbers.
Example 2:
Input: nums = [3,2,8,5,4,14,9,15]
Output: 8
Explanation:
The whole array has bitwise XOR 0 and contains 4 even and 4 odd numbers.
Example 3:
Input: nums = [0]
Output: 0
Explanation:
No non-empty subarray satisfies both conditions.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109Problem Overview: You are given an array of integers and need to find the maximum length subarray whose XOR result is balanced (effectively zero). The task is to identify the longest contiguous segment where the cumulative XOR cancels out.
Approach 1: Brute Force Enumeration (O(n2) time, O(1) space)
The simplest approach checks every possible subarray. Start from each index i, keep a running XOR while expanding the end index j, and update the maximum length whenever the XOR becomes 0. This works because the XOR of a subarray can be computed incrementally as you extend the window. The downside is quadratic time since every starting index explores all remaining elements. This method is useful for verifying correctness or understanding how XOR behaves over ranges in an array, but it does not scale for large inputs.
Approach 2: Prefix XOR + Hash Table (O(n) time, O(n) space)
The optimal solution uses the prefix XOR concept. Maintain a running value prefixXor where prefixXor[i] represents the XOR of elements from index 0 to i. If two indices have the same prefix XOR, the XOR of the subarray between them is zero because the values cancel out. Store the first occurrence of each prefix XOR in a hash table. When the same XOR appears again at index i, the subarray between the stored index and i has XOR equal to zero. Update the maximum length accordingly.
This method relies on the associative property of XOR and the ability to compare prefix states efficiently. Each element is processed once, and hash lookups are constant time on average. The algorithm combines ideas from prefix sum techniques with bit manipulation, making it both efficient and interview-friendly.
Recommended for interviews: Start by describing the brute force method to show you understand how XOR behaves across subarrays. Then move to the prefix XOR + hash table optimization. Interviewers expect the O(n) solution because it demonstrates familiarity with prefix techniques and hash-based indexing patterns commonly used for subarray problems.
We use a hash table to record the first occurrence position of each state (a, b), where a represents the prefix XOR sum, and b represents the prefix even count minus the prefix odd count. When we encounter the same state (a, b) while traversing the array, it means that the subarray from the last occurrence of this state to the current position satisfies both bitwise XOR equals 0 and equal counts of even and odd numbers. We can then update the answer by taking the maximum length. Otherwise, we store this state and the current position in the hash table.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray XOR | O(n^2) | O(1) | Small arrays or validating logic while learning XOR properties |
| Prefix XOR + Hash Table | O(n) | O(n) | General case and expected interview solution for large inputs |
Find Maximum Balanced XOR Subarray Length | LeetCode 3755 | Weekly Contest 477 • Sanyam IIT Guwahati • 866 views views
Watch 7 more video solutions →Practice Find Maximum Balanced XOR Subarray Length with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor