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. Consider the following Python code for grouping anagrams. What is the value of anagram_map after processing the input ["eat", "tea", "bat"]?

easy

A. [["eat", "tea"], ["bat"]]

B. [["eat"], ["tea"], ["bat"]]

C. [["eat", "bat"], ["tea"]]

D. [["bat", "tea"], ["eat"]]

Solution

1. Step 1: Trace first string "eat"

   Count array increments for 'e', 'a', 't'. Key tuple created and "eat" added to anagram_map[key].

2. Step 2: Trace second string "tea"

   Count array matches "eat"'s key, so "tea" appended to same list.

3. Step 3: Trace third string "bat"

   Count array differs, new key created, "bat" added to new list.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   "eat" and "tea" grouped, "bat" separate [OK]

Hint: Anagrams share identical frequency count keys [OK]

Common Mistakes:

• Confusing keys causing separate groups
• Appending to wrong list
• Off-by-one in count array

2. Given the following Python code for a time-based key-value store, what is the output of tm.get("foo", 3) after the shown operations?

easy

A. "bar"

B. ""

C. IndexError

D. "foo"

Solution

1. Step 1: Trace bisect_right on times=[1] with timestamp=3

   bisect_right returns the insertion point to the right of 3, which is index 1.

2. Step 2: Determine returned value

   Since i=1, return values[i-1] = values[0] = "bar".

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   bisect_right returns 1, so value at index 0 is "bar" [OK]

Hint: bisect_right returns insertion index; value at i-1 is correct [OK]

Common Mistakes:

• Returning empty string if timestamp > max stored
• Off-by-one error in index
• Confusing bisect_left with bisect_right

3. What is the time complexity of the optimal solution that uses a frequency map and first occurrence index to find the first unique character in a string of length n?

medium

A. O(n^2) because of nested loops to check duplicates

B. O(n) because it iterates over the string twice and uses constant-time hash operations

C. O(n) but with O(n) auxiliary space for frequency and index maps

D. O(n log n) due to sorting the characters by their first occurrence

Solution

1. Step 1: Identify loops and data structures used

   The algorithm iterates over the string twice: once to build frequency and index maps, once to find minimum index.

2. Step 2: Analyze time and space complexity

   Time is O(n) due to linear scans; space is O(n) for frequency and index dictionaries (worst case all unique).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time with linear auxiliary space for maps [OK]

Hint: Frequency and index maps use O(n) space, not O(1) [OK]

Common Mistakes:

• Confusing time with space complexity
• Assuming O(1) space due to limited charset
• Thinking sorting is involved

4. Consider the following buggy code for finding the first unique character index. Which line contains the subtle bug that causes incorrect results when duplicates are non-adjacent?

def firstUniqChar(s: str) -> int:
    freq = {}
    for i, ch in enumerate(s):
        if ch not in freq:
            freq[ch] = 1
        else:
            freq[ch] += 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return ch
    return -1

medium

A. Line 9: returning the character instead of its index

B. Line 3: initializing frequency dictionary incorrectly

C. Line 7: incrementing frequency count incorrectly

D. Line 11: returning -1 instead of 0 when no unique character

Solution

1. Step 1: Analyze return statement in second loop

   The code returns the character itself instead of its index, violating problem requirements.

2. Step 2: Confirm other lines are correct

   Frequency counting and increments are correct; returning -1 when no unique char is standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Return value must be index, not character [OK]

Hint: Return index, not character [OK]

Common Mistakes:

• Returning character instead of index
• Not handling no unique char case
• Incorrect frequency updates

5. Suppose the time-based key-value store is extended to allow multiple values to be set at the same timestamp for a key, and get should return the most recently set value at or before the timestamp. Which modification to the data structure and retrieval algorithm is correct?

hard

A. Store multiple values per timestamp in a list and modify binary search to find the last value in that list.

B. Store timestamps with duplicates in a list and use bisect_right to find insertion index, then return the last inserted value at that timestamp.

C. Store all (timestamp, value) pairs in insertion order and perform linear search backward on get.

D. Use a hash map from (key, timestamp) to a stack of values and pop on get.

Solution

1. Step 1: Understand requirement for multiple values per timestamp

   Multiple values at same timestamp require storing duplicates and retrieving the most recent one.

2. Step 2: Analyze retrieval with duplicates

   Using bisect_right on timestamps list with duplicates returns insertion index after all duplicates; returning value at i-1 gives the last inserted value at that timestamp.

3. Step 3: Confirm data structure modification

   Storing timestamps with duplicates in order and values aligned allows correct retrieval without linear search or complex structures.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   bisect_right with duplicates returns correct index for last inserted value [OK]

Hint: bisect_right handles duplicates by returning insertion after last duplicate [OK]

Common Mistakes:

• Using linear search causing inefficiency
• Using stacks requiring pop on get
• Storing multiple values in nested lists complicates retrieval