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. You need to find the length of the longest substring in a string that contains at most two distinct characters. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force approach checking all substrings with nested loops and counting distinct characters each time.

B. Use a sliding window with a frequency map to track character counts and adjust window size dynamically.

C. Use dynamic programming to store results of substrings and build up the solution.

D. Use a greedy approach that always picks the next character if it doesn't increase distinct count beyond two.

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest substring with at most two distinct characters, which suggests a variable-length window that expands and contracts based on distinct character count.

2. Step 2: Identify suitable algorithm

   Sliding window with a frequency map efficiently tracks character counts and distinct characters, allowing O(n) time complexity by adjusting window boundaries dynamically.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with frequency map is the classic optimal approach for this problem [OK]

Hint: Sliding window tracks distinct chars in O(n) time [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with substring problems
• Assuming greedy always works

2. You are given an array of positive integers and a target value x. You want to remove elements from the start and/or end of the array so that the sum of removed elements equals x. Which approach guarantees finding the minimum number of removals efficiently?

easy

A. Use a greedy approach removing the largest elements first from either end until sum equals x.

B. Find the longest subarray whose sum equals total sum minus x using a sliding window, then subtract its length from the array length.

C. Use dynamic programming to find all combinations of prefix and suffix sums that add up to x.

D. Try all possible combinations of removing elements from the start and end using nested loops.

Solution

1. Step 1: Understand the problem transformation

   The problem of removing elements from the ends summing to x is equivalent to finding a subarray in the middle with sum = totalSum - x.

2. Step 2: Recognize the sliding window pattern

   Finding the longest subarray with sum = target (totalSum - x) can be done in O(n) using a sliding window, which leads to minimum removals = array length - longest subarray length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window finds longest subarray efficiently [OK]

Hint: Transform to longest subarray sum problem [OK]

Common Mistakes:

• Trying greedy removal from ends fails on some cases
• Brute force is too slow for large inputs
• Dynamic programming overcomplicates the problem

3. The following code attempts to check if an array can be paired such that sums are divisible by k. Which line contains a subtle bug that causes incorrect results on some inputs?

def canArrange(nums, k):
    if len(nums) % 2 != 0:
        return True
    freq = {}
    for num in nums:
        r = ((num % k) + k) % k
        freq[r] = freq.get(r, 0) + 1
    if freq.get(0, 0) % 2 != 0:
        return False
    for r in freq:
        if r != 0:
            complement = (k - r) % k
            if freq.get(r, 0) != freq.get(complement, 0):
                return False
    if k % 2 == 0 and freq.get(k // 2, 0) % 2 != 0:
        return False
    return True

medium

A. Line 5: computing remainder without adjusting for negative numbers

B. Line 2: returning True when array length is odd

C. Line 8: checking if freq[0] count is even

D. Line 13: checking if freq[k//2] count is even when k is even

Solution

1. Step 1: Check array length condition

   The code returns True if the array length is odd, but pairing requires even length. This causes incorrect True on odd-length arrays.

2. Step 2: Verify other lines

   Remainder calculation correctly adjusts for negative numbers. Other checks for freq[0] and freq[k//2] are correct.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Odd length arrays cannot be fully paired, so returning True is a bug [OK]

Hint: Array length must be even to form pairs [OK]

Common Mistakes:

• Returning True on odd length arrays
• Not adjusting modulo for negative numbers
• Ignoring freq[0] or freq[k/2] parity checks

4. What is the time complexity of the optimal hash map with prefix sum remainders approach for the Continuous Subarray Sum problem, assuming the input array length is n and the divisor is k?

medium

A. O(n * k) due to nested loops over array and modulo values

B. O(n^2) because of checking all subarrays implicitly via prefix sums

C. O(n) because each element is processed once and hash map operations are O(1) on average

D. O(k) since the remainder map size is limited by k

Solution

1. Step 1: Analyze the loop and hash map operations

   The algorithm iterates over the array once (O(n)) and performs O(1) average-time hash map lookups and insertions.

2. Step 2: Consider the size of the remainder map

   The remainder map size is at most min(n, k), but this does not increase the iteration count beyond O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) time [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing prefix sums with nested loops
• Assuming modulo k adds multiplicative factor
• Ignoring average O(1) hash map operations

5. The following code attempts to implement the optimized sliding window approach for minimum window substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line assigning min_window = s[l:r+1]

B. Line incrementing formed when window_count[c] == t_count[c]

C. Line decrementing window_count[filtered_s[l][1]] inside while loop

D. Line filtering characters into filtered_s

Solution

1. Step 1: Identify substring extraction logic

   The code uses indices l and r as pointers over filtered_s, not original string s. Using s[l:r+1] extracts substring from index l to r in s, which is incorrect because l and r are indices in filtered_s, not s.

2. Step 2: Correct substring extraction

   Correct substring should use filtered_s[l][0] and filtered_s[r][0] to map back to original string indices: s[filtered_s[l][0]:filtered_s[r][0]+1].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect substring indexing causes wrong or runtime errors [OK]

Hint: Check if substring indices map to original string [OK]

Common Mistakes:

• Using filtered indices directly on original string
• Not updating formed count correctly