Contiguous Array (Equal 0s and 1s)

▶

Steps

setup

Initialize prefix_sum and hash map

We start with prefix_sum set to 0 and initialize the hash map with the entry {0: -1} to represent the prefix sum before the array starts.

💡 Initializing prefix_sum to 0 and storing it at index -1 allows us to handle subarrays starting at index 0 correctly.

Line:

prefix_sum = 0
seen = {0: -1}
max_length = 0

💡 This setup ensures that when prefix_sum returns to 0 at any index, the subarray from start to that index is balanced.

traverse

Process index 0, num = 0: update prefix_sum

At index 0, the number is 0, so we subtract 1 from prefix_sum, changing it from 0 to -1.

💡 We treat 0 as -1 to track the balance between 0s and 1s using prefix sums.

Line:

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

💡 Updating prefix_sum this way lets us detect when the number of 0s and 1s are equal by checking for repeated prefix sums.

insert

prefix_sum -1 not in hash map, insert it

Since prefix_sum -1 is not in the hash map, we insert the entry {-1: 0} to record the earliest index where -1 occurred.

💡 Storing the earliest index for each prefix_sum helps calculate subarray lengths later.

Line:

else:
    seen[prefix_sum] = i

💡 This insertion records the first occurrence of prefix_sum -1 at index 0.

traverse

Process index 1, num = 1: update prefix_sum

At index 1, the number is 1, so we add 1 to prefix_sum, changing it from -1 back to 0.

💡 Adding 1 for a 1 balances the previous subtraction for 0, potentially indicating a balanced subarray.

Line:

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

💡 The prefix_sum returning to 0 means the subarray from index 0 to 1 has equal 0s and 1s.

compare

prefix_sum 0 found in hash map, update max_length

Since prefix_sum 0 was seen before at index -1, we calculate the subarray length as 1 - (-1) = 2 and update max_length to 2.

💡 Finding a repeated prefix_sum means the subarray between the previous index and current index is balanced.

Line:

if prefix_sum in seen:
    max_length = max(max_length, i - seen[prefix_sum])

💡 This step shows how repeated prefix sums help find the longest balanced subarray efficiently.

reconstruct

End of iteration, return max_length

After processing all elements, we return max_length which is 2, the length of the longest contiguous subarray with equal 0s and 1s.

💡 The final max_length is the answer to the problem.

Line:

return max_length

💡 The algorithm efficiently finds the longest balanced subarray by leveraging prefix sums and hash map lookups.

prune

Extra step: Confirm no further elements

We confirm that the input array has been fully processed and no further prefix sums or updates are needed.

💡 This step ensures the algorithm terminates correctly after processing all elements.

Line:

for i, num in enumerate(nums):
    # loop ends here

💡 The algorithm completes after iterating through all elements.

reconstruct

Final answer is 2

The maximum length of a contiguous subarray with equal 0s and 1s is 2, which corresponds to the entire input array.

💡 This confirms the algorithm correctly identifies the longest balanced subarray.

Line:

return max_length

💡 The answer matches the expected output for the input [0,1].

reconstruct

Summary: prefix sums and hash map entries

The hash map contains prefix sums 0 and -1 with their earliest indices, showing how the algorithm tracked balance points.

💡 Reviewing the hash map entries helps solidify understanding of prefix sum storage.

Line:

# no code executed here, summary step

💡 The prefix sums stored correspond to points where the count of 0s and 1s were balanced or shifted.

reconstruct

End of visualization

The visualization ends with the final answer and the hash map state reflecting all prefix sums processed.

💡 This final step wraps up the trace and confirms the algorithm's output.

Line:

# end of function

💡 The algorithm's correctness and efficiency are demonstrated through the prefix sum and hash map approach.

def findMaxLength(nums):
    prefix_sum = 0  # STEP 1
    seen = {0: -1}  # STEP 1
    max_length = 0  # STEP 1
    for i, num in enumerate(nums):  # STEP 2 and 4
        prefix_sum += 1 if num == 1 else -1  # STEP 2 or 4
        if prefix_sum in seen:  # STEP 5
            max_length = max(max_length, i - seen[prefix_sum])  # STEP 5
        else:  # STEP 3
            seen[prefix_sum] = i  # STEP 3
    return max_length  # STEP 6

if __name__ == '__main__':
    print(findMaxLength([0,1]))  # Expected output: 2

📊

Contiguous Array (Equal 0s and 1s) - Watch the Algorithm Execute, Step by Step

Watching each step of the prefix sum and hash map updates reveals the core insight of the algorithm: equal numbers of 0s and 1s correspond to repeated prefix sums, which lets us find the longest balanced subarray efficiently.

insert

0→-1

Result: 0

check

Lookup: -1

0→-1

Result: 0

insert

Lookup: -1

0→-1

-1→0lookup

Result: 0

check

Lookup: 0→ -1

0→-1lookup

-1→0

Result: 0

lookup

Lookup: 0→ -1

0→-1lookup

-1→0

Result: 2

check

0→-1

-1→0

Result: 2

check

0→-1

-1→0

Result: 2

check

0→-1

-1→0

Result: 2

check

0→-1

-1→0

Result: 2

check

0→-1

-1→0

Result: 2

Key Takeaways

✓ Repeated prefix sums indicate balanced subarrays with equal numbers of 0s and 1s.

This insight is hard to see from code alone because it requires understanding the prefix sum concept and how it relates to subarray balance.

✓ Storing the earliest index of each prefix sum allows efficient calculation of maximum subarray lengths.

Visualizing the hash map entries clarifies why we only store the first occurrence of each prefix sum.

✓ Updating max_length only when a prefix sum repeats shows how the algorithm finds the longest balanced subarray without checking all subarrays.

The trace demonstrates the decision branching clearly, which is less obvious in the code.

Practice

1. Given the following code and input nums = [3,1,1,1,5], x = 5, what is the returned value?

easy

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate totalSum and target

   totalSum = 3+1+1+1+5 = 11; target = 11 - 5 = 6.

2. Step 2: Use sliding window to find longest subarray summing to 6

   Window expands: [3] sum=3, [3,1] sum=4, [3,1,1] sum=5, [3,1,1,1] sum=6 -> max_len=4; next, add 5 sum=11 > 6, shrink from left: remove 3 sum=8 >6, remove 1 sum=7 >6, remove 1 sum=6 -> max_len=4 remains (subarray [1,1,1]).

3. Step 3: Calculate minimum operations

   Minimum removals = array length - max_len = 5 - 4 = 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Longest subarray length 4 -> min ops = 1 [OK]

Hint: Sliding window finds longest subarray sum [OK]

Common Mistakes:

• Off-by-one errors in window length calculation
• Miscomputing sums when shrinking window
• Confusing min operations with longest subarray length

2. What is the time complexity of the optimal approach that counts subarrays with maximum bounded by left and right using the subtraction of two counts (countAtMost)?

medium

A. O(n) because it makes two linear passes over the array

B. O(n^2) because it checks all subarrays explicitly

C. O(n log n) due to sorting the array before counting

D. O(n) with O(n) extra space to store intermediate counts

Solution

1. Step 1: Identify operations in countAtMost

   countAtMost iterates over the array once, updating counters in O(1) time per element.

2. Step 2: Analyze overall complexity

   numSubarrayBoundedMax calls countAtMost twice, each O(n), so total time is O(n). No sorting or nested loops involved.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans -> O(n) time, constant space [OK]

Hint: Two linear scans, no nested loops or sorting [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking extra space is O(n)

3. Suppose the problem is modified so that the array can contain negative numbers, and you still need to find a continuous subarray of length at least 2 whose sum is a multiple of k. Which modification to the optimal approach is necessary to handle negative numbers correctly?

hard

A. Use a hash map to store all prefix sums instead of remainders modulo k

B. Adjust the modulo operation to handle negative remainders by adding k before modulo

C. No modification needed; the existing prefix sum remainder approach works unchanged

D. Switch to brute force since negative numbers break the remainder pattern

Solution

1. Step 1: Understand modulo behavior with negative numbers

   In many languages, modulo of negative numbers can be negative, causing incorrect remainder keys.

2. Step 2: Adjust modulo to always produce non-negative remainders

   By adding k before modulo (e.g., (running_sum % k + k) % k), remainders remain consistent and hash map keys valid.

3. Step 3: Confirm no other approach is needed

   Prefix sums and remainder hashing still work; only modulo adjustment is required.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling negative modulo correctly preserves remainder map logic [OK]

Hint: Normalize modulo to non-negative for negative numbers [OK]

Common Mistakes:

• Assuming no change needed
• Switching to brute force unnecessarily
• Storing full prefix sums instead of remainders

4. Suppose the problem changes: now you want the longest substring with at most two distinct characters, but characters can be reused infinitely many times and the input string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Maintain a sliding window with frequency counts but optimize by using a fixed-size array for frequencies instead of a hash map.

B. Use a brute force nested loop approach with early breaks to handle reuse.

C. Use a priority queue to track the least recently used character to evict when distinct count exceeds two.

D. Switch to a dynamic programming approach that stores results for substrings with reuse allowed.

Solution

1. Step 1: Understand reuse and input size impact

   Characters can be reused infinitely, but the problem remains longest substring with at most two distinct chars. The input is very long, so efficiency is critical.

2. Step 2: Identify efficient data structure

   Using a fixed-size array for frequencies (size 128 for ASCII) is more efficient than a hash map, reducing overhead and ensuring O(n) time and O(1) space.

3. Step 3: Confirm approach correctness

   The sliding window logic remains the same, but frequency tracking is optimized for speed and memory, suitable for very long inputs with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Fixed-size array frequency tracking is optimal for large inputs with limited charset [OK]

Hint: Fixed-size array beats hash map for fixed charset [OK]

Common Mistakes:

• Using brute force despite input size
• Using complex data structures unnecessarily
• Switching to DP without need

5. Suppose the problem is modified so that characters in t can be reused unlimited times in the substring (i.e., the substring must contain at least one occurrence of each character in t, but counts do not matter). Which of the following algorithmic changes correctly adapts the sliding window approach?

hard

A. Keep frequency counts but ignore counts when checking if window is valid; only check presence of characters

B. No changes needed; the original frequency counting approach works as is

C. Use the original frequency map and formed count but reset formed to zero after each window

D. Use a set to track presence of required characters and expand/shrink window until all are present

Solution

1. Step 1: Understand problem change

   Now only presence of each character in t is required, not counts. So frequency counts are unnecessary; presence tracking suffices.

2. Step 2: Adapt algorithm

   Using a set to track which required characters are currently in the window allows efficient checking. Expand window until all required chars are present, then shrink to minimize.

3. Step 3: Why other options fail

   Ignoring counts but keeping frequency maps wastes time and complicates logic. Resetting formed to zero after each window breaks continuity. Original approach requires exact counts, so no changes is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Presence tracking with sets fits the relaxed requirement [OK]

Hint: Presence tracking replaces frequency counting [OK]

Common Mistakes:

• Ignoring that counts no longer matter
• Trying to reuse frequency counts unnecessarily