Module 06 · Prefix Sums, Prefix State, and Difference Arrays

056. Equal Zeros and Ones

Bridge · Download this solution · All solutions and shared helpers

Problem

For a binary list, return (longest_length, count) over all nonempty subarrays containing equally many zeros and ones. Empty input returns (0,0). This expanded kata includes both objectives suggested by the compressed source.

Examples

Example 1

equal_binary_subarrays([0, 1, 0])
=> (2, 2)

Two length-two intervals are balanced.

Example 2

equal_binary_subarrays([0, 0])
=> (0, 0)

No interval contains a one.

Example 3

equal_binary_subarrays([])
=> (0, 0)

Both objectives have empty-input neutral answers.

Reveal the worked solution and reasoning

Why this mechanism works

Map a zero to -1 and a one to +1. Equal counts then mean zero transformed sum, so two equal prefix balances delimit a valid interval. Keep both the earliest boundary for maximum length and the frequency of boundaries for the count.

State and boundaries

balance is ones minus zeros. earliest supports longest intervals; frequency supports counting all intervals.

Protocol

Seed balance zero at boundary zero with frequency one.
Apply +1 or -1 per bit.
Count earlier equal balances.
Compare against the earliest equal boundary.
Preserve earliest and increment frequency.

Visualization

bits:     0  1  0
balance:0 -1  0 -1
equal boundaries -> intervals [0,2), [1,3)

Python implementation

def equal_binary_subarrays(nums):
    earliest, frequency = {0: 0}, {0: 1}
    balance = longest = count = 0
    for right, bit in enumerate(nums, 1):
        balance += 1 if bit == 1 else -1
        count += frequency.get(balance, 0)
        if balance in earliest:
            longest = max(longest, right - earliest[balance])
        earliest.setdefault(balance, right)
        frequency[balance] = frequency.get(balance, 0) + 1
    return longest, count

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

equal_binary_subarrays([0, 1, 0])

L2 equal_binary_subarrays: earliest, frequency = {0: 0}, {0: 1}
nums=[0, 1, 0]; earliest={0:0}; frequency={0:1}

L3 equal_binary_subarrays: balance = longest = count = 0
nums=[0, 1, 0]; earliest={0:0}; frequency={0:1}; balance=0; longest=0; count=0

L4 equal_binary_subarrays: for right, bit in enumerate(nums, 1):
nums=[0, 1, 0]; earliest={0:0}; frequency={0:1}; balance=0; longest=0; count=0; right=1; bit=0

L5 equal_binary_subarrays: balance += 1 if bit == 1 else -1
nums=[0, 1, 0]; earliest={0:0}; frequency={0:1}; balance=-1; longest=0; count=0; right=1; bit=0

L9 equal_binary_subarrays: earliest.setdefault(balance, right)
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:1}; balance=-1; longest=0; count=0; right=1; bit=0

L10 equal_binary_subarrays: frequency[balance] = frequency.get(balance, 0) + 1
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:1, -1:1}; balance=-1; longest=0; count=0; right=1; bit=0

L4 equal_binary_subarrays: for right, bit in enumerate(nums, 1):
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:1, -1:1}; balance=-1; longest=0; count=0; right=2; bit=1

L5 equal_binary_subarrays: balance += 1 if bit == 1 else -1
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:1, -1:1}; balance=0; longest=0; count=0; right=2; bit=1

... 3 intermediate state changes omitted ...

L4 equal_binary_subarrays: for right, bit in enumerate(nums, 1):
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:2, -1:1}; balance=0; longest=2; count=1; right=3; bit=0

L5 equal_binary_subarrays: balance += 1 if bit == 1 else -1
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:2, -1:1}; balance=-1; longest=2; count=1; right=3; bit=0

L6 equal_binary_subarrays: count += frequency.get(balance, 0)
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:2, -1:1}; balance=-1; longest=2; count=2; right=3; bit=0

L10 equal_binary_subarrays: frequency[balance] = frequency.get(balance, 0) + 1
nums=[0, 1, 0]; earliest={0:0, -1:1}; frequency={0:2, -1:2}; balance=-1; longest=2; count=2; right=3; bit=0

Result: (2, 2). Two length-two intervals are balanced.

equal_binary_subarrays([0, 0])

L2 equal_binary_subarrays: earliest, frequency = {0: 0}, {0: 1}
nums=[0, 0]; earliest={0:0}; frequency={0:1}

L3 equal_binary_subarrays: balance = longest = count = 0
nums=[0, 0]; earliest={0:0}; frequency={0:1}; balance=0; longest=0; count=0

L4 equal_binary_subarrays: for right, bit in enumerate(nums, 1):
nums=[0, 0]; earliest={0:0}; frequency={0:1}; balance=0; longest=0; count=0; right=1; bit=0

L5 equal_binary_subarrays: balance += 1 if bit == 1 else -1
nums=[0, 0]; earliest={0:0}; frequency={0:1}; balance=-1; longest=0; count=0; right=1; bit=0

L9 equal_binary_subarrays: earliest.setdefault(balance, right)
nums=[0, 0]; earliest={0:0, -1:1}; frequency={0:1}; balance=-1; longest=0; count=0; right=1; bit=0

L10 equal_binary_subarrays: frequency[balance] = frequency.get(balance, 0) + 1
nums=[0, 0]; earliest={0:0, -1:1}; frequency={0:1, -1:1}; balance=-1; longest=0; count=0; right=1; bit=0

L4 equal_binary_subarrays: for right, bit in enumerate(nums, 1):
nums=[0, 0]; earliest={0:0, -1:1}; frequency={0:1, -1:1}; balance=-1; longest=0; count=0; right=2; bit=0

L5 equal_binary_subarrays: balance += 1 if bit == 1 else -1
nums=[0, 0]; earliest={0:0, -1:1}; frequency={0:1, -1:1}; balance=-2; longest=0; count=0; right=2; bit=0

L9 equal_binary_subarrays: earliest.setdefault(balance, right)
nums=[0, 0]; earliest={0:0, -1:1, -2:2}; frequency={0:1, -1:1}; balance=-2; longest=0; count=0; right=2; bit=0

L10 equal_binary_subarrays: frequency[balance] = frequency.get(balance, 0) + 1
nums=[0, 0]; earliest={0:0, -1:1, -2:2}; frequency={0:1, -1:1, -2:1}; balance=-2; longest=0; count=0; right=2; bit=0

Result: (0, 0). No interval contains a one.

Why the solution is correct

Equal prefix balances mean the intervening interval has net contribution zero, exactly equal numbers of zeros and ones. Every matching earlier boundary counts once, while the earliest maximizes length. The two summaries answer different objectives over the same valid intervals.

Time and space

O(n) expected time and O(n) auxiliary space.

Common mistakes

Treating zero as contribution zero measures the number of ones instead of balance. Overwriting earliest breaks the length result even if the count stays correct.

Reasoning card

State: balance is ones minus zeros. earliest supports longest intervals; frequency supports counting all intervals.

Invariant: The prefix balance is ones minus zeros through the current point.

Decision to rehearse: Repeated prefix balance means the middle balances to zero.

Finish: Preserve earliest and increment frequency

Transfer exercise

For three symbols, store a pair of count differences and count subarrays with equal counts of all three.