Count Number of Nice Subarrays

▶

Steps

setup

Initialize pointers and counters for at_most_k(nums, 3)

Set left pointer to 0, count of valid subarrays to 0, and odd_count to 0 before starting the iteration over nums.

💡 Initialization sets the starting state for the sliding window before expanding the right pointer.

Line:

left = 0
count = 0
odd_count = 0

💡 Starting with an empty window and zero counts is essential for correct accumulation.

fill_cells

Expand right pointer to 0, check if nums[0] is odd

Move right pointer to index 0. nums[0] is 1, which is odd, so increment odd_count to 1.

💡 Expanding the window includes the first element and updates odd_count accordingly.

Line:

for right in range(len(nums)):
    if nums[right] % 2 == 1:
        odd_count += 1

💡 The window now contains one odd number, which affects whether we need to shrink the window later.

fill_cells

Add subarrays ending at right=0 to count

Calculate number of valid subarrays ending at right=0: right - left + 1 = 1. Add 1 to count.

💡 Counting subarrays ending at current right pointer accumulates total valid subarrays with at most k odd numbers.

Line:

count += right - left + 1

💡 Every subarray ending at right and starting between left and right is valid since odd_count <= k.

fill_cells

Expand right pointer to 1, nums[1] is odd, increment odd_count

Move right pointer to index 1. nums[1] is 1 (odd), so increment odd_count to 2.

💡 Expanding window includes another odd number, increasing odd_count.

Line:

if nums[right] % 2 == 1:
    odd_count += 1

💡 Tracking odd_count is crucial to know when to shrink the window.

fill_cells

Add subarrays ending at right=1 to count

Calculate valid subarrays ending at right=1: right - left + 1 = 2. Add 2 to count (total now 3).

💡 Counting all valid subarrays ending at current right pointer.

Line:

count += right - left + 1

💡 All subarrays starting from left to right are valid since odd_count <= k.

fill_cells

Expand right pointer to 2, nums[2] is even, odd_count unchanged

Move right pointer to index 2. nums[2] is 2 (even), so odd_count remains 2.

💡 Even numbers do not affect odd_count, so window can expand without shrinking.

Line:

if nums[right] % 2 == 1:
    odd_count += 1

💡 Only odd numbers affect the window's odd_count and potential shrinking.

fill_cells

Add subarrays ending at right=2 to count

Calculate valid subarrays ending at right=2: right - left + 1 = 3. Add 3 to count (total now 6).

💡 Counting all valid subarrays ending at current right pointer.

Line:

count += right - left + 1

💡 Window size increases count by number of new subarrays ending at right.

fill_cells

Expand right pointer to 3, nums[3] is odd, increment odd_count to 3

Move right pointer to index 3. nums[3] is 1 (odd), increment odd_count to 3.

💡 Adding an odd number increases odd_count, approaching the limit k=3.

Line:

if nums[right] % 2 == 1:
    odd_count += 1

💡 odd_count now equals k, so window is valid but cannot expand odd_count further without shrinking.

fill_cells

Add subarrays ending at right=3 to count

Calculate valid subarrays ending at right=3: right - left + 1 = 4. Add 4 to count (total now 10).

💡 Counting all valid subarrays ending at current right pointer.

Line:

count += right - left + 1

💡 All subarrays starting from left to right are valid since odd_count <= k.

fill_cells

Expand right pointer to 4, nums[4] is odd, increment odd_count to 4

Move right pointer to index 4. nums[4] is 1 (odd), increment odd_count to 4, which exceeds k=3.

💡 Window now has too many odd numbers, triggering shrinking from the left.

Line:

if nums[right] % 2 == 1:
    odd_count += 1

💡 When odd_count exceeds k, we must shrink the window to restore validity.

shrink

Shrink left pointer from 0 to 1 because odd_count > k

Since odd_count is 4 > 3, move left pointer from 0 to 1. nums[0] is odd, so decrement odd_count to 3.

💡 Shrinking the window removes an odd number to restore validity.

Line:

while odd_count > k:
    if nums[left] % 2 == 1:
        odd_count -= 1
    left += 1

💡 Shrinking ensures the window contains at most k odd numbers again.

fill_cells

Add subarrays ending at right=4 to count after shrinking

Now odd_count <= k, count subarrays ending at right=4: right - left + 1 = 4. Add 4 to count (total now 14).

💡 After shrinking, count all valid subarrays ending at right pointer.

Line:

count += right - left + 1

💡 Shrinking allows counting valid subarrays that include the new right element.

reconstruct

Complete at_most_k(3) with count = 14

Finished iterating over nums for at_most_k(3). The total count of subarrays with at most 3 odd numbers is 14.

💡 This count includes all subarrays with 0 to 3 odd numbers.

Line:

return count

💡 This value will be used to compute the exact count of subarrays with exactly k odd numbers.

setup

Initialize pointers and counters for at_most_k(nums, 2)

Reset left, count, and odd_count to 0 to compute at_most_k(2) for subtraction.

💡 We compute at_most_k(k-1) to subtract from at_most_k(k) for exact count.

Line:

left = 0
count = 0
odd_count = 0

💡 Resetting state is necessary for the second call.

fill_cells

Expand right pointer to 0, nums[0] is odd, increment odd_count to 1

Move right pointer to 0. nums[0] is odd, increment odd_count to 1.

💡 Start counting subarrays with at most 2 odd numbers.

Line:

for right in range(len(nums)):
    if nums[right] % 2 == 1:
        odd_count += 1

💡 Tracking odd_count again for the new k value.

fill_cells

Add subarrays ending at right=0 to count

Add 1 subarray ending at right=0 to count (total now 1).

💡 Counting valid subarrays for k=2.

Line:

count += right - left + 1

💡 Counting subarrays incrementally.

fill_cells

Expand right pointer to 1, nums[1] is odd, increment odd_count to 2

Move right pointer to 1. nums[1] is odd, increment odd_count to 2.

💡 Window now has at most 2 odd numbers, still valid.

Line:

if nums[right] % 2 == 1:
    odd_count += 1

💡 Tracking odd_count for window validity.

fill_cells

Add subarrays ending at right=1 to count

Add 2 subarrays ending at right=1 to count (total now 3).

💡 Counting valid subarrays for k=2.

Line:

count += right - left + 1

💡 Incremental counting of valid subarrays.

shrink

Shrink window when odd_count exceeds 2 at right=4

At right=4, odd_count would become 4 if expanded fully. Shrink left pointer to maintain odd_count <= 2.

💡 Shrinking window to keep odd_count within limit for k=2.

Line:

while odd_count > k:
    if nums[left] % 2 == 1:
        odd_count -= 1
    left += 1

💡 Window adjusts dynamically to maintain constraints.

reconstruct

Complete at_most_k(2) with count = 12 and compute final answer

Finished at_most_k(2) with count 12. Compute final answer: 14 (at_most_k(3)) - 12 (at_most_k(2)) = 2.

💡 Subtracting counts gives number of subarrays with exactly k odd numbers.

Line:

return at_most_k(nums, k) - at_most_k(nums, k - 1)

💡 Final answer is the difference of counts for at most k and at most k-1 odd numbers.

def at_most_k(nums, k):  # STEP 1,14
    left = 0  # STEP 1,14
    count = 0  # STEP 1,14
    odd_count = 0  # STEP 1,14
    for right in range(len(nums)):  # STEP 2-12,15-19
        if nums[right] % 2 == 1:  # STEP 2,4,6,8,10,15,17
            odd_count += 1  # STEP 2,4,6,8,10,15,17
        while odd_count > k:  # STEP 11,19
            if nums[left] % 2 == 1:  # STEP 11,19
                odd_count -= 1  # STEP 11,19
            left += 1  # STEP 11,19
        count += right - left + 1  # STEP 3,5,7,9,12,16,18
    return count  # STEP 13,20

def count_nice_subarrays(nums, k):  # STEP 20
    return at_most_k(nums, k) - at_most_k(nums, k - 1)  # STEP 20

if __name__ == '__main__':
    print(count_nice_subarrays([1,1,2,1,1], 3))  # Output: 2

📊

Count Number of Nice Subarrays - Watch the Algorithm Execute, Step by Step

Watching each pointer move and count update helps you understand how the algorithm efficiently counts valid subarrays without enumerating all subarrays.

insert

left→0

count→0

odd_count→0

right→null

increment

left→0

right→0

odd_count→1

count→0

update

left→0

right→0

odd_count→1

count→1

increment

left→0

right→1

odd_count→2

count→1

update

left→0

right→1

odd_count→2

count→3

check

left→0

right→2

odd_count→2

count→3

update

left→0

right→2

odd_count→2

count→6

increment

left→0

right→3

odd_count→3

count→6

update

left→0

right→3

odd_count→3

count→10

increment

left→0

right→4

odd_count→4

count→10

decrement

left→1

right→4

odd_count→3

count→10

update

left→1

right→4

odd_count→3

count→14

return

count→14

Result: 14

insert

left→0

count→0

odd_count→0

right→null

increment

left→0

right→0

odd_count→1

count→0

update

left→0

right→0

odd_count→1

count→1

increment

left→0

right→1

odd_count→2

count→1

update

left→0

right→1

odd_count→2

count→3

decrement

left→2

right→4

odd_count→2

count→8

update

at_most_k_3→14

at_most_k_2→12

answer→2

Result: 2

Key Takeaways

✓ The sliding window efficiently counts subarrays with at most k odd numbers by expanding and shrinking pointers.

This insight is hard to see from code alone because the dynamic window size and odd_count updates are subtle.

✓ Counting subarrays ending at each right pointer as right - left + 1 accumulates all valid subarrays incrementally.

Visualizing this counting step clarifies why we don't need to enumerate all subarrays explicitly.

✓ Subtracting counts of at most k and at most k-1 odd numbers yields the exact count of subarrays with exactly k odd numbers.

This mathematical trick is not obvious without seeing the two separate counts and their difference.

Practice

1. Consider the following code snippet for finding the longest contiguous subarray with equal 0s and 1s. What is the value of max_length returned for input [0, 1, 0]?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace prefix_sum and seen dictionary for each index

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}; Index 1: num=1 -> prefix_sum=0, max_length=1-(-1)=2; Index 2: num=0 -> prefix_sum=-1, max_length=max(2,2-0)=2.

2. Step 2: Return max_length after full iteration

   max_length is 2, corresponding to subarray [0,1] or [1,0].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums correctly track balance; max_length updated only when prefix_sum repeats [OK]

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

Common Mistakes:

• Off-by-one in max_length calculation
• Not initializing seen with 0:-1
• Updating max_length incorrectly

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 optimized sliding window approach with character filtering for the minimum window substring problem, given n = len(s) and m = len(t)?

medium

A. O(n) because each character in s is visited at most twice after filtering

B. O(n * m) due to nested loops over s and t

C. O(n + m) due to filtering and frequency map operations

D. O(n^2) because shrinking and expanding windows can overlap quadratically

Solution

1. Step 1: Analyze filtering and iteration

   Filtering s to only characters in t takes O(n). The main loop iterates over filtered_s, which is at most n. Each character is visited at most twice by left and right pointers.

2. Step 2: Confirm sliding window complexity

   Sliding window moves right pointer forward and left pointer forward independently, each at most n times. Frequency map updates and checks are O(1) per operation. The total complexity is O(n + m) because counting frequencies of t takes O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window with filtering runs in linear time relative to s length plus frequency map setup [OK]

Hint: Sliding window pointers each move linearly [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing filtering cost with main loop cost

4. 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

5. Suppose the input array can contain multiple repeated elements and you want to find the longest subarray with equal number of 0s and 1s, but now elements can be reused multiple times (like a circular array). Which modification to the prefix sum approach correctly handles this scenario?

hard

A. Use a sliding window with two pointers to find balanced subarrays in the circular array.

B. Reset prefix sums and first_occurrence after each full pass to handle reuse.

C. Extend the array by concatenating it to itself and run the prefix sum algorithm on the doubled array.

D. Modify prefix sums to be modulo n and track first occurrences modulo n.

Solution

1. Step 1: Recognize circular array means subarrays can wrap around.

   Doubling the array simulates wrap-around by linearizing circular behavior.

2. Step 2: Run prefix sum algorithm on doubled array to find longest balanced subarray crossing boundary.

   This preserves O(n) complexity and correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Other options break correctness or do not handle wrap-around properly [OK]

Hint: Double array to handle circular subarrays [OK]

Common Mistakes:

• Resetting prefix sums loses info
• Modulo prefix sums break balance detection
• Sliding window can't detect all wrap-around cases