Subarray with Equal Number of 0s and 1s

▶

Steps

setup

Initialize variables and prefix sum array

We initialize the length n, create the first_occurrence array filled with -2 (meaning unseen), and set the offset to n. This sets up the data structure to track prefix sums.

💡 Setting all entries to -2 means no prefix sums have been seen yet, and offset centers prefix sums around zero for indexing.

Line:

n = len(nums)
first_occurrence = [-2] * (2 * n + 1)
offset = n

💡 The prefix sum array size and offset allow indexing prefix sums from -n to +n safely.

setup

Set prefix sum 0 occurrence at offset index

We record that prefix sum 0 is first seen at index -1 by setting first_occurrence[offset] = -1.

💡 This base case allows subarrays starting at index 0 to be counted correctly when prefix sum zero is encountered again.

Line:

first_occurrence[offset] = -1

💡 Marking prefix sum 0 at -1 helps calculate lengths of subarrays starting from the beginning.

traverse

Start iterating: i=0, num=0, update prefix sum

At index 0, the number is 0, so prefix_sum decreases by 1 to -1.

💡 We convert 0 to -1 to track balance between 0s and 1s via prefix sums.

Line:

prefix_sum += -1 if num == 0 else 1

💡 Prefix sums reflect the net count difference between 1s and 0s seen so far.

insert

Record first occurrence of prefix sum -1

Since prefix sum -1 (index 1) was unseen (-2), we record its first occurrence at index 0.

💡 Recording first occurrence allows future subarrays with the same prefix sum to calculate length.

Line:

first_occurrence[prefix_sum + offset] = i

💡 Storing earliest index for prefix sums is crucial for length calculation.

traverse

Next iteration: i=1, num=1, update prefix sum

At index 1, number is 1, so prefix_sum increases by 1 to 0.

💡 Adding 1 for a 1 balances the previous -1, returning prefix sum to zero.

Line:

prefix_sum += -1 if num == 0 else 1

💡 Prefix sum zero means equal number of 0s and 1s so far.

compare

Prefix sum 0 seen before, update max_length

Prefix sum 0 was first seen at index -1, so subarray length is 1 - (-1) = 2. max_length updates to 2.

💡 Repeated prefix sums mean the subarray between occurrences is balanced.

Line:

max_length = max(max_length, i - first_occurrence[prefix_sum + offset])

💡 The length between repeated prefix sums is the length of a balanced subarray.

traverse

End of iteration: no more elements

All elements processed; max_length is 2, representing the longest balanced subarray.

💡 The algorithm finishes after processing all elements, having tracked prefix sums and max length.

Line:

return max_length

💡 The final max_length is the answer to the problem.

reconstruct

Return final answer

The function returns max_length = 2, the length of the longest subarray with equal 0s and 1s.

💡 Returning the max_length completes the algorithm and provides the solution.

Line:

return max_length

💡 The final answer is derived from the prefix sum tracking process.

reconstruct

Summary: prefix sums and max length

The prefix sums tracked were -1 at index 0 and 0 at index -1 and 1. The longest balanced subarray length found is 2.

💡 This step summarizes the key tracked data and final result.

Line:

# no code, summary step

💡 Understanding the prefix sums and their first occurrences explains the max length result.

reconstruct

Final state with answer

The final state shows the prefix sum array unchanged and the answer 2 as the longest balanced subarray length.

💡 This final visualization confirms the algorithm's output and the data structure state.

Line:

# final return

💡 The answer is the maximum length found during prefix sum tracking.

def findMaxLength(nums):
    n = len(nums)  # STEP 1
    first_occurrence = [-2] * (2 * n + 1)  # STEP 1
    offset = n  # STEP 1
    first_occurrence[offset] = -1  # STEP 2
    prefix_sum = 0
    max_length = 0
    for i, num in enumerate(nums):  # STEP 3,5
        prefix_sum += -1 if num == 0 else 1  # STEP 3,5
        if first_occurrence[prefix_sum + offset] >= -1:  # STEP 6
            max_length = max(max_length, i - first_occurrence[prefix_sum + offset])  # STEP 6
        else:
            first_occurrence[prefix_sum + offset] = i  # STEP 4
    return max_length  # STEP 7,8

📊

Subarray with Equal Number of 0s and 1s - Watch the Algorithm Execute, Step by Step

Watching each prefix sum update and lookup helps you understand how the algorithm efficiently detects balanced subarrays without checking all subarrays explicitly.

insert

0→-2

1→-2

2→-2

3→-2

4→-2

Result: 0

insert

0→-2

1→-2

2→-1

3→-2

4→-2

Result: 0

lookup

Lookup: 1→ -2

0→-2

1→-2lookup

2→-1

3→-2

4→-2

Result: 0

insert

Lookup: 1→ -2

0→-2

1→0lookup

2→-1

3→-2

4→-2

Result: 0

lookup

Lookup: 2→ -1

0→-2

1→0

2→-1lookup

3→-2

4→-2

Result: 0

lookup

Lookup: 2→ -1

0→-2

1→0

2→-1lookup

3→-2

4→-2

Result: 2

check

0→-2

1→0

2→-1

3→-2

4→-2

Result: 2

check

0→-2

1→0

2→-1

3→-2

4→-2

Result: 2

check

0→-2

1→0

2→-1

3→-2

4→-2

Result: 2

check

0→-2

1→0

2→-1

3→-2

4→-2

Result: 2

Key Takeaways

✓ Tracking prefix sums and their first occurrences allows efficient detection of balanced subarrays without checking all subarrays.

This insight is hard to see from code alone because the connection between prefix sums and subarray balance is subtle.

✓ Repeated prefix sums indicate subarrays with equal numbers of 0s and 1s between their first and current occurrences.

Visualizing prefix sums as keys in a map clarifies why repeated sums correspond to balanced subarrays.

✓ Initializing prefix sum 0 at index -1 is crucial to correctly count subarrays starting at index 0.

This special case is easy to miss in code but becomes obvious when watching the visualization.

Practice

1. Consider the following code snippet for finding the longest arithmetic subsequence length. What is the value of max_len after processing the input [1, 3, 5, 7]?

easy

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Trace dp updates for input [1,3,5,7]

   For each pair (j,i), difference is 2, subsequence lengths increase: dp[1][2]=2, dp[2][2]=3, dp[3][2]=4.

2. Step 2: Confirm max_len tracks the longest subsequence length

   max_len updates to 2, then 3, then 4 as longer subsequences are found.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest arithmetic subsequence length is 4 for difference 2 [OK]

Hint: Longest arithmetic subsequence length equals 4 for evenly spaced input [OK]

Common Mistakes:

• Off-by-one error in initializing prev_len
• Confusing subsequence length with number of pairs
• Returning 0 or 1 incorrectly for small inputs

2. The following code attempts to solve the Continuous Subarray Sum problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: updating remainder_map[running_sum] = i before checking condition

B. Line 11: verifying subarray length > 1

C. Line 9: checking if running_sum in remainder_map

D. Line 3: initializing running_sum to 0

Solution

1. Step 1: Understand remainder_map update timing

   The original code updated remainder_map[running_sum] = i before checking if running_sum already exists, overwriting the earliest index.

2. Step 2: Identify consequence of overwriting

   Overwriting earliest index causes missing longer subarrays that satisfy the condition, leading to false negatives.

3. Step 3: Correct the code

   Update remainder_map[running_sum] = i only if running_sum is not already in remainder_map, preserving earliest occurrence.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct code inserts remainder only if not present to preserve earliest index [OK]

Hint: Earliest remainder index must be preserved to find valid subarrays [OK]

Common Mistakes:

• Updating remainder map on every occurrence
• Not checking subarray length >= 2
• Modulo by zero errors

3. What is the time complexity of the optimal sliding window solution for finding the longest substring with at most two distinct characters, assuming the input string length is n?

medium

A. O(n²), because the inner while loop can run up to n times for each character.

B. O(n * k), where k is the number of distinct characters allowed (here k=2).

C. O(n log n), due to maintaining a balanced data structure for frequencies.

D. O(n), because each character is visited at most twice by the left and right pointers.

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once. The left pointer only moves forward when distinct_count > 2, also at most n times.

2. Step 2: Confirm total operations

   Each character is processed at most twice (once when right pointer visits, once when left pointer moves), so total operations are O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with two pointers is classic O(n) approach [OK]

Hint: Two pointers each move at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to O(n²)
• Confusing frequency map maintenance cost
• Thinking k affects complexity linearly

4. Suppose the problem is modified so that the input array can contain multiple values (not just 0 and 1), and you want the longest contiguous subarray where the count of two chosen values is equal. Which approach correctly adapts the prefix sum + hash map method?

hard

A. Use a hash map to track counts of all values and check equality at each step with nested loops.

B. Transform one chosen value to +1, the other to -1, and ignore other values; then apply prefix sum + hash map.

C. Use prefix sums for each value separately and find overlapping intervals with equal sums.

D. Apply the original prefix sum method directly without changes, treating all non-chosen values as zeros.

Solution

1. Step 1: Reduce problem to tracking difference between counts of two chosen values

   Map one chosen value to +1, the other to -1, and treat other values as 0 (ignored).

2. Step 2: Apply prefix sum + hash map on transformed array

   This allows detecting subarrays where counts of chosen values are equal by prefix sums returning to same value.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Other options either ignore other values incorrectly or require nested loops [OK]

Hint: Transform problem to difference of two values with +1/-1 mapping [OK]

Common Mistakes:

• Trying to track all counts simultaneously
• Ignoring other values incorrectly
• Using nested loops for large inputs

5. Suppose the input list to summaryRanges can contain duplicates and is not guaranteed sorted. Which modification ensures correct output with minimal overhead?

hard

A. Sort the input and remove duplicates before applying the two-pointer approach.

B. Use a hash map to count occurrences and then build ranges from keys in arbitrary order.

C. Apply the two-pointer approach directly without sorting, since duplicates don't affect ranges.

D. Use nested loops to check every pair for consecutive sequences, ignoring duplicates.

Solution

1. Step 1: Understand input constraints

   Duplicates and unsorted input break the assumption that consecutive elements are adjacent.

2. Step 2: Modify input to fit algorithm

   Sorting and removing duplicates ensures input is sorted unique, allowing two-pointer approach to work correctly.

3. Step 3: Evaluate other options

   Hash map keys unordered, so ranges can't be built correctly; applying two-pointer without sorting fails; nested loops are inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + deduplication restores preconditions for linear scan [OK]

Hint: Sort and deduplicate before two-pointer scan [OK]

Common Mistakes:

• Ignoring sorting requirement
• Using hash map keys unordered
• Applying two-pointer on unsorted input