LeetCode 3755 - Find Maximum Balanced XOR Subarray Length
This problem asks us to find the longest contiguous subarray that simultaneously satisfies two independent conditions: 1. The bitwise XOR of all elements in the subarray is equal to 0. 2. The subarray contains an equal number of even and odd elements.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation, Prefix Sum
Solution
LeetCode 3755 - Find Maximum Balanced XOR Subarray Length
Problem Understanding
This problem asks us to find the longest contiguous subarray that simultaneously satisfies two independent conditions:
- The bitwise XOR of all elements in the subarray is equal to
0. - The subarray contains an equal number of even and odd elements.
We are given an array nums, and we must return the maximum length among all subarrays that satisfy both requirements. If no valid subarray exists, we return 0.
The XOR condition is a classic prefix XOR problem. For a subarray nums[l..r], its XOR can be computed from prefix XOR values. Specifically, the XOR of a subarray is zero exactly when the prefix XOR before the subarray is equal to the prefix XOR after the subarray.
The parity balance condition can also be transformed into a prefix problem. If we treat odd numbers as +1 and even numbers as -1, then a subarray contains equal numbers of odd and even elements exactly when the sum of these transformed values is zero.
The array length can be as large as 10^5, which immediately rules out algorithms that examine all possible subarrays. Since there are O(n²) possible subarrays, a brute force solution would be far too slow. The constraints strongly suggest that we need a linear or near-linear solution.
Several edge cases are worth noting:
- A single element can never be balanced because it cannot contain equal counts of even and odd numbers.
- A subarray may satisfy the XOR condition but fail the parity condition.
- A subarray may satisfy the parity condition but fail the XOR condition.
- The answer may be the entire array.
- There may be no valid subarray at all, in which case we return
0. - Elements may be as large as
10^9, but XOR operations remain efficient because they operate on fixed-width integers.
Approaches
Brute Force
A straightforward approach is to examine every possible subarray.
For each starting index, we extend the ending index one position at a time while maintaining:
- The XOR of the current subarray.
- The count of even numbers.
- The count of odd numbers.
Whenever the XOR becomes zero and the even count equals the odd count, we update the answer.
This approach is correct because it explicitly checks every possible subarray. However, there are O(n²) subarrays, making the solution far too slow for n = 100000.
Key Insight
The two conditions can both be expressed using prefix states.
For XOR:
- Let
px[i]be the XOR of the firstielements. - A subarray
(l, r]has XOR zero when:
px[l] = px[r]
For parity balance:
- Convert each odd number into
+1. - Convert each even number into
-1. - Let
balance[i]be the prefix sum of these values. - A subarray has equal numbers of even and odd elements when:
balance[l] = balance[r]
Therefore, a subarray satisfies both conditions exactly when:
px[l] = px[r]balance[l] = balance[r]
This means we only need to find the farthest pair of indices having the same state:
(prefixXor, balance)
For every position, we record the earliest index where a state first appeared. When the same state appears again, the subarray between those positions satisfies both conditions. Using the earliest occurrence maximizes the subarray length.
This gives a linear-time solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Checks every subarray directly |
| Optimal | O(n) | O(n) | Uses prefix XOR and prefix balance states |
Algorithm Walkthrough
- Initialize
prefix_xor = 0. - Initialize
balance = 0, where:
- odd contributes
+1 - even contributes
-1
- Create a hash map that stores the earliest index where each state
(prefix_xor, balance)appears. - Insert the initial state:
- state
(0, 0) - index
-1
This represents the empty prefix before the array begins. 5. Iterate through the array from left to right. 6. For each element:
-
Update
prefix_xorusing XOR. -
Update
balance: -
+1if odd -
-1if even
- Form the current state:
(prefix_xor, balance)
- If this state has been seen before:
- Let the earliest index be
j. - The subarray
(j + 1 ... current)satisfies both conditions. - Update the answer with:
current_index - j
9. Otherwise, store the current index as the first occurrence of this state.
10. Continue until all elements have been processed.
11. Return the maximum length found.
Why it Works
For any two positions i and j, if the prefix XOR values are equal, then the XOR of the elements between them is zero. Similarly, if the prefix balance values are equal, then the number of odd elements equals the number of even elements between them. Therefore, whenever both prefix values match, the subarray between those positions satisfies both required conditions. Storing the earliest occurrence of each state guarantees that every matching state produces the longest possible subarray ending at the current position.
Python Solution
from typing import List, Tuple
class Solution:
def maxBalancedSubarray(self, nums: List[int]) -> int:
prefix_xor = 0
balance = 0
max_length = 0
first_seen: dict[Tuple[int, int], int] = {(0, 0): -1}
for i, num in enumerate(nums):
prefix_xor ^= num
if num & 1:
balance += 1
else:
balance -= 1
state = (prefix_xor, balance)
if state in first_seen:
max_length = max(max_length, i - first_seen[state])
else:
first_seen[state] = i
return max_length
The implementation maintains two prefix values while scanning the array once.
prefix_xor tracks the XOR of all elements processed so far. balance tracks the difference between odd and even counts. Every position is represented by the pair (prefix_xor, balance).
The hash map stores the earliest index where each state appears. When the same state is encountered again, both the XOR condition and parity condition are automatically satisfied for the subarray between the two occurrences.
Because each element is processed exactly once and every hash map operation is constant time on average, the solution runs in linear time.
Go Solution
package main
func maxBalancedSubarray(nums []int) int {
prefixXor := 0
balance := 0
maxLength := 0
type State struct {
xor int
balance int
}
firstSeen := map[State]int{
{0, 0}: -1,
}
for i, num := range nums {
prefixXor ^= num
if num&1 == 1 {
balance++
} else {
balance--
}
state := State{
xor: prefixXor,
balance: balance,
}
if idx, exists := firstSeen[state]; exists {
if i-idx > maxLength {
maxLength = i - idx
}
} else {
firstSeen[state] = i
}
}
return maxLength
}
The Go implementation follows the same logic as the Python version. Since Go maps cannot use tuples directly, a small struct is used as the hash key. The struct contains both the prefix XOR and balance values. Go integers are sufficient because XOR values remain within the range of the input constraints and balance values are bounded by ±n.
Worked Examples
Example 1
Input
nums = [3,1,3,2,0]
Initial state:
| Index | prefix_xor | balance | State |
|---|---|---|---|
| -1 | 0 | 0 | (0,0) |
Processing:
| i | num | prefix_xor | balance | State | Action |
|---|---|---|---|---|---|
| 0 | 3 | 3 | 1 | (3,1) | store |
| 1 | 1 | 2 | 2 | (2,2) | store |
| 2 | 3 | 1 | 3 | (1,3) | store |
| 3 | 2 | 3 | 2 | (3,2) | store |
| 4 | 0 | 3 | 1 | (3,1) | seen at index 0 |
At index 4:
length = 4 - 0 = 4
Answer:
4
Example 2
Input
nums = [3,2,8,5,4,14,9,15]
The running state eventually returns to:
(prefix_xor, balance) = (0,0)
at index 7.
Since (0,0) first appeared at index -1:
length = 7 - (-1) = 8
Answer:
8
Example 3
Input
nums = [0]
Processing:
| i | num | prefix_xor | balance | State |
|---|---|---|---|---|
| 0 | 0 | 0 | -1 | (0,-1) |
No state repeats.
Answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Single pass through the array |
| Space | O(n) | Hash map may store a unique state for every prefix |
The algorithm processes each element exactly once. Every iteration performs only a few arithmetic operations and hash map lookups. The hash map can contain up to one entry per prefix position, resulting in linear auxiliary space.
Test Cases
sol = Solution()
assert sol.maxBalancedSubarray([3, 1, 3, 2, 0]) == 4 # example 1
assert sol.maxBalancedSubarray([3, 2, 8, 5, 4, 14, 9, 15]) == 8 # example 2
assert sol.maxBalancedSubarray([0]) == 0 # example 3
assert sol.maxBalancedSubarray([1, 1]) == 0 # all odd
assert sol.maxBalancedSubarray([2, 2]) == 0 # all even
assert sol.maxBalancedSubarray([1, 1, 2, 2]) == 4 # whole array valid
assert sol.maxBalancedSubarray([5, 5]) == 2 # xor zero and balanced
assert sol.maxBalancedSubarray([7, 7, 2, 2]) == 4 # repeated xor cancellations
assert sol.maxBalancedSubarray([1, 2, 3, 4]) == 0 # balanced parity but xor nonzero
assert sol.maxBalancedSubarray([1, 2]) == 0 # balanced parity but xor nonzero
assert sol.maxBalancedSubarray([5, 5, 8, 8]) == 4 # entire array valid
assert sol.maxBalancedSubarray([0, 1, 1, 0]) == 4 # xor zero and balanced
assert sol.maxBalancedSubarray([10**9, 10**9, 1, 1]) == 4 # large values
assert sol.maxBalancedSubarray([3, 2, 1, 0, 3, 2, 1, 0]) == 8 # long valid array
Test Summary
| Test | Why |
|---|---|
[3,1,3,2,0] |
Official example 1 |
[3,2,8,5,4,14,9,15] |
Official example 2 |
[0] |
Official example 3 |
[1,1] |
No even numbers |
[2,2] |
No odd numbers |
[1,1,2,2] |
Entire array valid |
[5,5] |
Smallest nontrivial valid subarray |
[7,7,2,2] |
Multiple XOR cancellations |
[1,2,3,4] |
Balance condition alone is insufficient |
[1,2] |
Minimal balanced parity case |
[5,5,8,8] |
Whole array satisfies both conditions |
[0,1,1,0] |
Includes zero values |
[10**9,10**9,1,1] |
Large numbers |
[3,2,1,0,3,2,1,0] |
Longer repeated pattern |
Edge Cases
No Valid Subarray Exists
Arrays such as [0], [1,1], or [2,2] do not contain any subarray satisfying both conditions. A common mistake is to assume XOR zero alone is enough. The algorithm only accepts a subarray when both the prefix XOR and prefix balance states match, so these cases correctly return 0.
Entire Array Is the Answer
Sometimes the entire array satisfies both conditions. For example, [5,5,8,8] has XOR zero and contains two odd and two even numbers. Initializing state (0,0) at index -1 allows the algorithm to detect subarrays that begin at index 0, including the entire array.
XOR Condition Holds but Balance Does Not
Consider [5,5]. The XOR is zero, but there are two odd numbers and zero even numbers, so the parity condition fails. The algorithm does not rely solely on prefix XOR. It requires the complete state (prefix_xor, balance) to match, preventing such false positives.
Large Integer Values
The constraint allows values up to 10^9. Since XOR operates directly on integer bit patterns and the algorithm never performs expensive operations based on value magnitude, large numbers do not affect correctness or complexity. The hash map simply stores the resulting prefix XOR values as part of the state key.