Contiguous Array (Equal 0s and 1s)

📋

Contiguous Array (Equal 0s and 1s)

Edge cases:

</>

IDE

def findMaxLength(nums: list[int]) -> int:public int findMaxLength(int[] nums)int findMaxLength(vector<int>& nums)function findMaxLength(nums)

def findMaxLength(nums):
    # Write your solution here
    pass

class Solution {
    public int findMaxLength(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMaxLength(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findMaxLength(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0 for input [0,1]Not updating max length when prefix sums match or missing initial prefix sum entry.✅ Initialize prefix sum map with sum 0 at index -1 and update max length when prefix sum repeats.

Wrong: Non-zero for empty inputNo base case for empty input causing incorrect return or crash.✅ Add base case to return 0 if input array is empty.

Wrong: Shorter length due to greedy approachStopping at first balanced subarray found instead of checking all.✅ Use prefix sums and hash map to find max length over all subarrays.

Wrong: Off-by-one length errorsIncorrect calculation of subarray length from indices.✅ Calculate length as current_index - first_occurrence_index.

Wrong: TLE on large inputUsing nested loops O(n^2) instead of O(n) prefix sum + hash map.✅ Implement prefix sum + hash map approach for O(n) time complexity.

✓

Test Cases

Try testing your solution on empty and minimal inputs to catch base cases.

Consider tricky distributions of zeros and ones that break greedy logic.

Optimize your solution to linear time using prefix sums and hash maps.

t1_01basic

Input{"nums":[0,1]}

Expected2

⏱ Performance - must finish in 2000ms

The entire array has equal number of 0s and 1s.

💡 Try transforming 0s to -1s and use prefix sums.

💡 Use a hash map to store first occurrence of prefix sums.

💡 Return the max distance between two equal prefix sums.

Why it failed: Returned incorrect length; likely missed updating max length when prefix sums match. Fix by tracking earliest prefix sum indices and updating max length accordingly.

✓ Correctly finds max length for the canonical example.

t1_02basic

Input{"nums":[0,1,0,1,1,1,0]}

Expected4

⏱ Performance - must finish in 2000ms

The longest subarray with equal 0s and 1s is [0,1,0,1,1,1,0] sub-subarray [0,1,0,1,1,1,0] has max balanced subarray length 6 (e.g. [0,1,0,1,1,1,0] from index 0 to 5).

💡 Consider prefix sums after converting 0 to -1.

💡 Store first occurrence indices of prefix sums in a hash map.

💡 Update max length when prefix sum repeats at a later index.

Why it failed: Incorrect max length; possibly not resetting counts or not using prefix sums correctly. Fix by using prefix sums and hash map to track earliest indices.

✓ Correctly computes max length for a longer array.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so max length is 0.

💡 Check how your code handles empty input.

💡 Ensure prefix sums and hash map handle zero-length arrays.

💡 Return 0 immediately if input is empty.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a base case to return 0 when nums is empty.

✓ Handles empty input gracefully.

t2_02edge

Input{"nums":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single element cannot have equal number of 0s and 1s.

💡 Check subarray lengths less than 2.

💡 No subarray of length 1 can be balanced.

💡 Return 0 if no balanced subarray found.

Why it failed: Returns non-zero for single element input. Fix by ensuring subarrays considered have length >= 2.

✓ Correctly returns 0 for single element input.

t2_03edge

Input{"nums":[0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All zeros means no equal number of 1s, so max length is 0.

💡 Check if your code handles arrays with no 1s.

💡 Prefix sums will never repeat for balanced subarray.

💡 Return 0 if no balanced subarray found.

Why it failed: Returns non-zero for all zeros input. Fix by ensuring prefix sums are correctly computed and max length updated only when sums repeat.

✓ Correctly returns 0 for all zeros input.

t2_04edge

Input{"nums":[1,1,1,1]}

Expected0

⏱ Performance - must finish in 2000ms

All ones means no equal number of 0s, so max length is 0.

💡 Check if your code handles arrays with no 0s.

💡 Prefix sums will never repeat for balanced subarray.

💡 Return 0 if no balanced subarray found.

Why it failed: Returns non-zero for all ones input. Fix by ensuring prefix sums are correctly computed and max length updated only when sums repeat.

✓ Correctly returns 0 for all ones input.

t3_01corner

Input{"nums":[0,0,1,1,0,1,1,0]}

Expected8

⏱ Performance - must finish in 2000ms

Entire array has equal number of 0s and 1s (4 zeros and 4 ones).

💡 Check if your code handles the entire array as a valid subarray.

💡 Prefix sums should be zero at the end if balanced.

💡 Ensure max length updates when prefix sum is zero at current index.

Why it failed: Fails to consider subarray starting at index 0. Fix by initializing prefix sum map with sum 0 at index -1.

✓ Correctly identifies entire array as longest balanced subarray.

t3_02corner

Input{"nums":[0,1,1,0,1,1,1,0]}

Expected4

⏱ Performance - must finish in 2000ms

Longest balanced subarray is length 6, not the first found subarray.

💡 Avoid greedy approaches that pick first balanced subarray found.

💡 Use prefix sums and hash map to find max length over all subarrays.

💡 Check all prefix sums and update max length accordingly.

Why it failed: Greedy approach returns shorter subarray length. Fix by using prefix sums and hash map to find max length over all subarrays.

✓ Correctly finds max balanced subarray length despite non-trivial distribution.

t3_03corner

Input{"nums":[0,1,0,1,0,1,0]}

Expected6

⏱ Performance - must finish in 2000ms

Longest balanced subarray is length 7, the entire array.

💡 Check off-by-one errors in subarray length calculation.

💡 Ensure max length is updated with current_index - first_occurrence_index.

💡 Verify prefix sum indices and length calculations.

Why it failed: Off-by-one error causes incorrect length. Fix by calculating length as current_index - first_occurrence_index.

✓ Correctly computes max length with accurate indexing.

t4_01performance

Input{"nums":[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) prefix sum + hash map solution must complete within 2 seconds.

💡 Use prefix sums and hash map for O(n) time complexity.

💡 Avoid nested loops which cause O(n^2) time.

💡 Store earliest prefix sum indices to update max length efficiently.

Why it failed: TLE due to nested loops or inefficient approach. Fix by implementing prefix sum + hash map solution with O(n) complexity.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Given the following code snippet, what is the final output when calling isHappy(7)?

def sum_of_squares(num):
    return sum(int(d) ** 2 for d in str(num))

UNHAPPY_CYCLE = {4, 16, 37, 58, 89, 145, 42, 20}

def isHappy(n: int) -> bool:
    while n != 1 and n not in UNHAPPY_CYCLE:
        n = sum_of_squares(n)
    return n == 1

print(isHappy(7))

easy

A. false

B. true

C. The code runs infinitely

D. Raises a runtime error

Solution

1. Step 1: Trace sum_of_squares for n=7

   7 -> 7² = 49

2. Step 2: Iterate until n=1 or cycle detected

   49 -> 4²+9²=16+81=97 -> 9²+7²=81+49=130 -> 1²+3²+0²=1+9+0=10 -> 1²+0²=1 -> loop ends, returns true

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   7 is a happy number, code returns true [OK]

Hint: Trace sum_of_squares until 1 or cycle [OK]

Common Mistakes:

• Assuming 7 leads to cycle or infinite loop

2. Consider the following Python function that finds the length of the longest subarray with sum divisible by k. What is the returned value when called with nums = [2, 7, 6, 1] and k = 5?

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        if remainder < 0:
            remainder += k
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace prefix sums and remainders

   nums = [2,7,6,1], k=5 - i=0: prefix_sum=2, remainder=2, earliest[2]=-2 -> earliest[2]=0 - i=1: prefix_sum=9, remainder=4, earliest[4]=-2 -> earliest[4]=1 - i=2: prefix_sum=15, remainder=0, earliest[0]=-1 -> max_length=max(0,2-(-1))=3 - i=3: prefix_sum=16, remainder=1, earliest[1]=-2 -> earliest[1]=3

2. Step 2: Final max_length is 3

   The longest subarray divisible by 5 has length 3 (from index 0 to 2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Longest subarray length = 3 [OK]

Hint: Track prefix sums and earliest remainder indices carefully [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Forgetting to initialize earliest[0] = -1
• Ignoring negative remainder adjustment

3. You are given an integer array and need to find the k elements that appear most frequently. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map and bucket sort to group elements by their frequency, then collect top k from highest frequency buckets.

B. Sort the entire array and pick the top k elements by frequency.

C. Use a greedy approach that picks elements as they appear until k elements are chosen.

D. Use dynamic programming to build frequency counts and select top k elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding top k frequent elements efficiently, ideally in linear time.

2. Step 2: Identify approach with linear time complexity

   Bucket sort groups elements by frequency, allowing O(n) time retrieval of top k elements by scanning buckets from high to low frequency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort approach is known to run in O(n) time for this problem [OK]

Hint: Bucket sort groups by frequency for O(n) retrieval [OK]

Common Mistakes:

• Sorting entire array is O(n log n), not optimal
• Greedy approach ignores frequency counts
• DP is unrelated to frequency counting here

4. Suppose the problem changes: now elements from the arrays can be reused multiple times in the intersection (i.e., unlimited reuse). Which modification to the algorithm correctly handles this new requirement?

hard

A. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection if count > 0 without decrementing counts.

B. Use the same two-pointer approach but do not increment pointers when elements match, allowing reuse.

C. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection and decrement count accordingly.

D. Sort both arrays and use two pointers, but reset pointers to zero after each match to allow reuse.

Solution

1. Step 1: Understand reuse requirement

   Elements can be reused unlimited times, so counts should not be decremented after matching.

2. Step 2: Evaluate modifications

   Two-pointer approach relies on moving pointers forward, so it cannot handle reuse without complex resets. Hash map counting without decrementing counts allows unlimited reuse correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map frequency counting without decrement handles reuse correctly [OK]

Hint: Do not decrement counts to allow reuse [OK]

Common Mistakes:

• Not changing pointer logic for reuse
• Decrementing counts incorrectly
• Resetting pointers causing infinite loops

5. Suppose the Two Sum problem is modified so that the same element can be used multiple times to reach the target sum. Which of the following approaches correctly solves this variant?

hard

A. Use the original hash map approach without changes; it works as is.

B. Sort the array and use two pointers, moving pointers only when sum is less or greater than target.

C. Use a dynamic programming approach similar to the coin change problem to allow reuse.

D. Use a brute force nested loop checking all pairs including pairs with the same index.

Solution

1. Step 1: Understand the reuse requirement

   Allowing reuse means the same element can be chosen multiple times, which breaks the original hash map approach that assumes distinct indices.

2. Step 2: Identify suitable algorithm

   Dynamic programming similar to coin change counts combinations allowing reuse, correctly handling multiple uses of the same element.

3. Step 3: Evaluate other options

   Original hash map fails reuse; two pointers assume distinct elements; brute force with same index pairs is invalid.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DP approach handles reuse correctly, unlike hash map or two pointers [OK]

Hint: Reuse requires DP, not hash map or two pointers [OK]

Common Mistakes:

• Assuming original hash map works with reuse
• Using two pointers without modification
• Allowing same index pairs in brute force