Find Maximum Balanced XOR Subarray Length solution and explanation
8 more videos on this problem
Find Maximum Balanced XOR Subarray Length | LeetCode 3755 | Weekly Contest 477Sanyam IIT Guwahati · 19:30 · 905 views
Find Maximum Balanced XOR Subarray Length | Weekly Contest 477 | Java| Developer CoderDeveloper Coder · 17:49 · 416 views
3755. Find Maximum Balanced XOR Subarray Length | HashMap | Weekly Contest 477 | LeetcodeRapid Syntax · 15:05 · 353 views
Leetcode 3755 🔥 Maximum Balanced XOR Subarray Length | Weekly Contest 477 Q2 | Map Approach Study Placement · 14:08 · 339 views
LeetCode Weekly Contest 477 | LeetCode 3754 | LeetCode 3755 | LeetCode 3756codeTips · 31:26 · 245 views
LeetCode 3755 | Find Maximum Balanced XOR Subarray Length | XOR + Prefix LogicCode Kage · 7:50 · 82 views
3755. Find Maximum Balanced XOR Subarray Length (Leetcode Medium)Programming Live with Larry · 12:09 · 55 views
Leetcode Weekly Contest 477 Q2. Find Maximum Balanced XOR Subarray Length #python #dsaADevOpsEngineer · 15:59 · 54 views
Find Maximum Balanced XOR Subarray Lengthshomali_thakur · 13:05 · 38 views
The problem
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] <= 109
Approach overview
Problem 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.
Solution
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.
class Solution:
def maxBalancedSubarray(self, nums: List[int]) -> int:
d = {(0, 0): -1}
a = b = 0
ans = 0
for i, x in enumerate(nums):
a ^= x
b += 1 if x % 2 == 0 else -1
if (a, b) in d:
ans = max(ans, i - d[(a, b)])
else:
d[(a, b)] = i
return ansclass Solution {
public int maxBalancedSubarray(int[] nums) {
Map<Long, Integer> d = new HashMap<>();
int ans = 0;
int a = 0, b = nums.length;
d.put((long) b, -1);
for (int i = 0; i < nums.length; ++i) {
a ^= nums[i];
b += nums[i] % 2 == 0 ? 1 : -1;
long key = (1L * a << 32) | b;
if (d.containsKey(key)) {
ans = Math.max(ans, i - d.get(key));
} else {
d.put(key, i);
}
}
return ans;
}
}class Solution {
public:
int maxBalancedSubarray(vector<int>& nums) {
unordered_map<long long, int> d;
int ans = 0;
int a = 0, b = nums.size();
d[(long long) b] = -1;
for (int i = 0; i < nums.size(); ++i) {
a ^= nums[i];
b += nums[i] % 2 == 0 ? 1 : -1;
long long key = (1LL * a << 32) | b;
if (d.contains(key)) {
ans = max(ans, i - d[key]);
} else {
d[key] = i;
}
}
return ans;
}
};function maxBalancedSubarray(nums: number[]): number {
const d = new Map<bigint, number>();
let ans = 0;
let a = 0;
let b = nums.length;
d.set(BigInt(b), -1);
for (let i = 0; i < nums.length; ++i) {
a ^= nums[i];
b += nums[i] % 2 === 0 ? 1 : -1;
const key = (BigInt(a) << 32n) | BigInt(b);
if (d.has(key)) {
ans = Math.max(ans, i - d.get(key)!);
} else {
d.set(key, i);
}
}
return ans;
}func maxBalancedSubarray(nums []int) (ans int) {
d := map[int64]int{}
a := 0
b := len(nums)
d[int64(b)] = -1
for i, x := range nums {
a ^= x
if x%2 == 0 {
b++
} else {
b--
}
key := int64(a)<<32 | int64(b)
if j, ok := d[key]; ok {
ans = max(ans, i-j)
} else {
d[key] = i
}
}
return
}Complexity analysis
| 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 |
Frequently asked questions
Is Find Maximum Balanced XOR Subarray Length easy or hard?
The problem is generally categorized as Medium difficulty. The main challenge is recognizing the prefix XOR pattern and using a hash map to track previously seen XOR states to achieve an O(n) solution.
Find Maximum Balanced XOR Subarray Length Python/Java solution
Most implementations compute a running prefix XOR and store indices in a dictionary or map. Python typically uses a dictionary, Java uses HashMap, C++ uses unordered_map, and Go or TypeScript use their respective map structures. All versions follow the same O(n) prefix XOR logic.
How to solve Find Maximum Balanced XOR Subarray Length in O(n)?
Maintain a running prefix XOR while iterating through the array. Store the earliest index where each XOR value appears in a hash map. If the same XOR value appears again at index i, the subarray between the stored index and i has XOR equal to zero. Update the maximum length using this distance.
What is the best approach for Find Maximum Balanced XOR Subarray Length?
The best approach uses prefix XOR with a hash table. Track the cumulative XOR while iterating through the array and store the first index where each XOR value appears. When the same XOR appears again, the subarray between the two indices has XOR equal to zero. This method runs in O(n) time and O(n) space.
Is Find Maximum Balanced XOR Subarray Length asked at Google/Amazon/Meta?
Prefix XOR and longest zero-XOR subarray patterns appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of prefix techniques, hash maps, and bit manipulation in subarray problems.
What data structure is used in Find Maximum Balanced XOR Subarray Length?
A hash table (hash map) is used to store the first occurrence of each prefix XOR value. This allows constant-time lookups to determine whether the same XOR state has appeared before and compute the corresponding subarray length.
What is the time complexity of Find Maximum Balanced XOR Subarray Length?
The optimal solution runs in O(n) time because each element is processed once while maintaining a prefix XOR and performing constant‑time hash table lookups. The brute force method takes O(n^2) time since it evaluates every possible subarray.