Skip to main content
Talentd

Find Maximum Balanced XOR Subarray Length - Solution & Explanation

MediumArrayHash TableBit ManipulationPrefix Sum8 min read
Practice this problem

Problem Statement

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 <= 105
  • 0 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray XORO(n^2)O(1)Small arrays or validating logic while learning XOR properties
Prefix XOR + Hash TableO(n)O(n)General case and expected interview solution for large inputs

Video Solution

Find Maximum Balanced XOR Subarray Length | LeetCode 3755 | Weekly Contest 477 • Sanyam IIT Guwahati • 905 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Find Maximum Balanced XOR Subarray Length with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays