Abstract / Summary

Count how many subarrays have an equal number of 0s and 1s.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 54% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Hash Table
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic problem of counting subarrays whose cumulative XOR equals zero. It does so by iterating once over the input list while maintaining a running XOR prefix and a frequency map of previously seen prefix values. Each time a prefix value repeats, the number of earlier occurrences contributes directly to the answer because any subarray bounded by two equal prefixes has a zero XOR.

Key Steps

Initialization

result = 0
total = 0
have = defaultdict(int)

result accumulates the final count. total holds the current prefix XOR. have is a dictionary that records how many times each prefix XOR has appeared so far. The dictionary is pre-populated implicitly with a count of zero for any unseen key.

Prefix Traversal

for n in [0] + nums:
    total ^= n
    result += have[total]
    have[total] += 1

The loop prepends a zero to the original list, which represents the empty prefix before any element is processed. Inside the loop the current element n is XORed into total, updating the prefix XOR. The current value of total is looked up in have; the stored count indicates how many earlier positions share the same prefix XOR. Each such earlier position defines a subarray ending at the current index with XOR zero, so the count is added to result. Finally, the frequency of the current prefix XOR is incremented.

Return

return result

After processing all elements, result holds the total number of zero-XOR subarrays and is returned.

Edge Cases Handled

When the input list is empty, the loop iterates over the single element [0]. The prefix XOR remains zero, have[0] is initially zero, and after the iteration have[0] becomes one. The result stays zero, correctly indicating that there are no subarrays in an empty array.

If the array contains a single element equal to zero, the loop processes [0, 0]. After the first iteration the prefix XOR is zero and have[0] becomes one. In the second iteration the prefix XOR stays zero, have[0] is one, so result is increased by one. This captures the subarray consisting of the single zero element.

When all elements are identical non-zero values, the XOR of any even-length subarray becomes zero. The prefix XOR toggles between the element value and zero, and the frequency map correctly records each occurrence, allowing the algorithm to count all qualifying subarrays without special casing.

Performance Optimizations

The algorithm runs in a single pass over the input, avoiding nested loops entirely. By using a hash map (defaultdict) to store prefix frequencies, each lookup and update occurs in constant average time, ensuring that the overall work scales linearly with the length of nums.

The inclusion of the leading zero in the iteration eliminates the need for a separate initialization step for the empty prefix, simplifying the loop body and reducing conditional checks.

Because the XOR operation is inexpensive and the dictionary stores only distinct prefix values, the memory footprint grows proportionally to the number of unique prefix XORs rather than to the square of the input size. This makes the solution efficient for large inputs with many repeated prefix values.

Imagine you have a long row of numbered toy blocks. Some blocks have special powers, and when you combine them in a certain way, they can turn into a magic zero. This code is like a little robot helper designed to look at every possible group of blocks sitting next to each other in that row.

The robot starts by thinking about the number zero because that is a safe place to begin. As it walks along the blocks, it keeps a running total of the magic power of all the blocks it has seen so far. Think of this like keeping a tally in a secret notebook. Every time the robot sees a new block, it updates its running total and checks its notebook to see if it has seen that same magic total before.

If the magic total has been seen before, it means there is a group of blocks in the middle that perfectly cancels everything out to become nothing. The robot counts these special groups and keeps track of how many it finds. It keeps doing this until it reaches the very end of the line of blocks, making sure it never misses a single group that hides a secret zero.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		C++	Java		Python		TS
	WalkCCC		C++	Java		Python
	leetcode.ca		C++	Java	Go	Python	Rust	TS
	Progiez		C++	Java		Python
github	charles-wangkai			Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality