Abstract / Summary

Find the maximum length of a subarray with an equal number of 0 and 1.

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 51% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• 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 finding the longest contiguous sub-array with an equal number of 0s and 1s. It does so by converting the original binary values into a running balance, where a 0 decrements the balance and a 1 increments it. The balance acts as a prefix-sum identifier: whenever the same balance reappears, the segment between the two occurrences contains an equal count of 0s and 1s. The algorithm records the earliest index at which each balance value is seen, then computes the length of any later segment that returns to that balance, keeping the maximum length found.

Key Steps and Corresponding Snippets

The first important step is the creation of a dictionary that will map each observed balance to the earliest index where it occurs. The dictionary is seeded with a balance of zero at a virtual index of -1, which enables detection of a valid sub-array that starts at the very first element.

first = dict()
first[0] = -1

Next, the algorithm initializes two variables: result to hold the best length discovered so far, and current to maintain the running balance while iterating through the input list.

result = 0
current = 0

The core of the solution is a single pass over the input array. For each element, the balance is adjusted: a 0 reduces it, while a 1 increases it. A debug print statement outputs the index and the new balance, which can be useful during development or troubleshooting.

for i in range(len(nums)):
    if nums[i] == 0:
        current -= 1
    else:
        current += 1
    print(i, "=", current)

After updating the balance, the algorithm checks whether this balance has been seen before. If it has, the distance between the current index and the earliest index stored for this balance represents a candidate sub-array length. The result variable is updated with the larger of its current value and this candidate length.

    if current in first:
        distance = i - first[current]
        result = max(result, distance)

If the balance is new, the algorithm records the current index as the first occurrence of this balance. Storing only the earliest index ensures that any later distance calculation yields the longest possible segment for that particular balance value.

    else:
        first[current] = i

Finally, after the loop completes, the function returns the maximum length found.

return result

Edge Cases Handled

The code gracefully handles an empty input list. Since the loop body never executes, result remains at its initial value of zero, which correctly indicates that no qualifying sub-array exists.

When the input consists entirely of zeros or entirely of ones, the running balance never repeats after its initial entry. Consequently, the if current in first branch never triggers a length update, and the function returns zero, reflecting the absence of a balanced sub-array.

The initialization first[0] = -1 specifically addresses the scenario where a balanced sub-array begins at index zero. By treating the virtual position before the array as having a balance of zero, the distance calculation i - first[current] correctly yields the length of a prefix that itself is balanced.

Alternating patterns such as [0, 1, 0, 1] produce frequent balance repetitions. The algorithm captures each repeat, computes the corresponding distances, and updates result accordingly, ultimately returning the full length of the array when the entire sequence is balanced.

Performance Optimizations Observed

The solution employs a hash map (dict) to store balance-to-index mappings, providing constant-time average lookups and insertions. This choice eliminates the need for nested loops or repeated scans of the array, ensuring that each element is processed exactly once.

By recording only the first occurrence of each balance, the algorithm avoids unnecessary overwrites and guarantees that any later distance calculation yields the longest possible segment for that balance. This strategy reduces the amount of stored data to at most one entry per distinct balance value, which is bounded by the length of the input.

The use of a single integer variable (current) to track the running balance avoids the overhead of constructing auxiliary prefix-sum arrays. This minimalistic state management keeps memory usage low and improves cache locality during iteration.

The debug print statement, while useful for tracing, can be redirected or disabled in production contexts without affecting the core logic, allowing the algorithm to retain its efficiency when such output is suppressed.

Imagine a line of colorful blocks where some are blue and some are red. This code is like a game to find the longest part of the line that has an equal number of blue and red blocks. To keep score, the code starts with a special bag called a dictionary to remember where it has been.

As it walks along the line of blocks from start to finish, it keeps a running count. If it picks up a blue block, the count goes up by one, and if it picks up a red block, the count goes down by one. Every time it finishes looking at a block, it checks the bag to see if it has seen this same count before. If the count matches a number already in the bag, it means the section between the old spot and the new spot has exactly the same number of red and blue blocks. It measures how far apart those two spots are and keeps track of the longest distance it finds during the whole trip. If the count is new, it saves the spot in the bag so it can remember it for later.

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		Python	JS			Go		TS
	LeetcodeHelp	C++	Java		Python
	MemoryLimitExceeded	C++			Python
	Progiez	C++	Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	everthis					JS
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan		Java
	halfrost								Go
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007				Python
	MacJim	C++
	ruoru						Rust
	shreymehul			C#
	suxrobGM			C#
	trung-hn				Python
	varunu28		Java
	vli02									C
	wisdompeak	C++
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
yuanliu666	Kotlin
zfang399	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