Count Number of Nice Subarrays (K Odd Numbers)

▶

Steps

setup

Initialize variables for countAtMost(nums, k)

Initialize count to 0, left pointer to 0, and odd_count to 0 before starting the sliding window.

💡 Setting these variables prepares to track the number of valid subarrays and window boundaries.

Line:

count = 0
left = 0
odd_count = 0

💡 We start with an empty window and no odd numbers counted.

expand

Expand right pointer to 0 and include nums[0] = 1 (odd)

Move right pointer to index 0, detect nums[0] is odd, increment odd_count to 1, then count subarrays ending at right=0.

💡 Expanding the window includes a new odd number, increasing the odd count inside the window, then counting valid subarrays.

Line:

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

💡 The window now contains one odd number, which is within the allowed limit k=3, contributing 1 valid subarray.

expand

Expand right pointer to 1 and include nums[1] = 1 (odd)

Move right pointer to index 1, increment odd_count to 2, then count subarrays ending at right=1.

💡 Window expands to include another odd number, increasing odd_count but still within limit, then counts valid subarrays.

Line:

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

💡 Window now contains 2 odd numbers, still valid for k=3, contributing 2 new valid subarrays.

expand

Expand right pointer to 2 and include nums[2] = 2 (even)

Move right pointer to index 2; nums[2] is even, so odd_count remains 2, then count subarrays ending at right=2.

💡 Including an even number does not change odd_count but expands the window, then counts valid subarrays.

Line:

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

💡 Window still valid with 2 odd numbers, contributing 3 new valid subarrays.

expand

Expand right pointer to 3 and include nums[3] = 1 (odd)

Move right pointer to index 3 and increment odd_count to 3 because nums[3] is odd, then count subarrays ending at right=3.

💡 Window now contains exactly k=3 odd numbers, still valid, then counts valid subarrays.

Line:

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

💡 Window is at the limit of allowed odd numbers, contributing 4 new valid subarrays.

expand

Expand right pointer to 4 and include nums[4] = 1 (odd), then shrink window

Move right pointer to index 4 and increment odd_count to 4 because nums[4] is odd, exceeding k=3. Then shrink window from left to restore validity.

💡 Window now has too many odd numbers, triggering shrink phase to remove odd numbers from the left.

Line:

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

💡 Window is invalid and must shrink from the left; after shrinking, window is valid again with 3 odd numbers, contributing 4 new valid subarrays.

prune

Finish countAtMost(nums, k) with result 14

All right indices processed; countAtMost(nums, 3) returns 14.

💡 This count includes all subarrays with at most 3 odd numbers.

Line:

return count

💡 We have the total count of subarrays with at most k odd numbers.

setup

Initialize variables for countAtMost(nums, k-1=2)

Reset count, left, and odd_count to 0 to count subarrays with at most 2 odd numbers.

💡 We repeat the sliding window process for k-1 to subtract from previous count.

Line:

count = 0
left = 0
odd_count = 0

💡 Starting fresh to count subarrays with at most 2 odd numbers.

expand

Expand right pointer to 0 and include nums[0] = 1 (odd)

Move right pointer to 0 and increment odd_count to 1, then count subarrays ending at right=0.

💡 Window expands with one odd number, valid for k-1=2, then counts valid subarrays.

Line:

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

💡 Window valid with 1 odd number, contributing 1 valid subarray.

expand

Expand right pointer to 1 and include nums[1] = 1 (odd)

Move right pointer to 1 and increment odd_count to 2, then count subarrays ending at right=1.

💡 Window now has 2 odd numbers, equal to k-1 limit, then counts valid subarrays.

Line:

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

💡 Window valid with 2 odd numbers, contributing 2 new valid subarrays.

expand

Expand right pointer to 2 and include nums[2] = 2 (even)

Move right pointer to 2; nums[2] is even, odd_count remains 2, then count subarrays ending at right=2.

💡 Including even number does not change odd_count, then counts valid subarrays.

Line:

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

💡 Window still valid with 2 odd numbers, contributing 3 new valid subarrays.

expand

Expand right pointer to 3 and include nums[3] = 1 (odd), then shrink window

Move right pointer to 3 and increment odd_count to 3, exceeding k-1=2. Then shrink window from left to restore validity.

💡 Window now invalid, must shrink from left to remove odd numbers and restore validity.

Line:

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

💡 Window invalid triggers shrink phase; after shrinking, window valid with 2 odd numbers, contributing 3 new valid subarrays.

expand

Expand right pointer to 4 and include nums[4] = 1 (odd), then shrink window

Move right pointer to 4 and increment odd_count to 3, exceeding k-1=2. Then shrink window from left to restore validity.

💡 Window invalid again, must shrink to remove odd numbers and restore validity.

Line:

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

💡 Window invalid triggers shrink phase; after shrinking, window valid with 2 odd numbers, contributing 3 new valid subarrays.

prune

Finish countAtMost(nums, k-1) with result 12

All right indices processed; countAtMost(nums, 2) returns 12.

💡 We have the count of subarrays with at most k-1 odd numbers.

Line:

return count

💡 Ready to compute final answer by subtracting counts.

reconstruct

Calculate final answer: countAtMost(k) - countAtMost(k-1)

Subtract 12 from 14 to get 2, the number of subarrays with exactly k=3 odd numbers.

💡 This subtraction isolates subarrays with exactly k odd numbers.

Line:

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

💡 Final answer is 2, matching expected output.

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

def countNiceSubarrays(nums, k):
    return countAtMost(nums, k) - countAtMost(nums, k - 1)  # STEP 28

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

📊

Count Number of Nice Subarrays (K Odd Numbers) - Watch the Algorithm Execute, Step by Step

Watching the window boundaries move and how the odd count changes is the fastest way to understand how the algorithm efficiently counts valid subarrays without enumerating all.

expand

L ▼

1

0

1

1

2

2

1

3

1

4

Metric: 0

Answer: 0

record_answer

L=R

1

0

1

1

2

2

1

3

1

4

Window: [1]

Metric: 1

Answer: 1

record_answer

L ▼

1

0

R ▼

1

1

2

2

1

3

1

4

Window: [1, 1]

Metric: 2

Answer: 3

record_answer

L ▼

1

0

1

1

R ▼

2

2

1

3

1

4

Window: [1, 1, 2]

Metric: 2

Answer: 6

record_answer

L ▼

1

0

1

1

2

2

R ▼

1

3

1

4

Window: [1, 1, 2, 1]

Metric: 3

Answer: 10

record_answer

1

0

L ▼

1

1

2

2

1

3

R ▼

1

4

Window: [1, 2, 1, 1]

Metric: 3

Answer: 14

prune

1

0

L ▼

1

1

2

2

1

3

R ▼

1

4

Window: [1, 2, 1, 1]

Metric: 3

Answer: 14

expand

L ▼

1

0

1

1

2

2

1

3

1

4

Metric: 0

Answer: 0

record_answer

L=R

1

0

1

1

2

2

1

3

1

4

Window: [1]

Metric: 1

Answer: 1

record_answer

L ▼

1

0

R ▼

1

1

2

2

1

3

1

4

Window: [1, 1]

Metric: 2

Answer: 3

record_answer

L ▼

1

0

1

1

R ▼

2

2

1

3

1

4

Window: [1, 1, 2]

Metric: 2

Answer: 6

record_answer

1

0

L ▼

1

1

2

2

R ▼

1

3

1

4

Window: [1, 2, 1]

Metric: 2

Answer: 9

record_answer

1

0

1

1

L ▼

2

2

1

3

R ▼

1

4

Window: [2, 1, 1]

Metric: 2

Answer: 12

prune

1

0

1

1

L ▼

2

2

1

3

R ▼

1

4

Window: [2, 1, 1]

Metric: 2

Answer: 12

record_answer

1

0

1

1

L ▼

2

2

1

3

R ▼

1

4

Window: [2, 1, 1]

Answer: 2

Key Takeaways

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

This insight is hard to see from code alone because the window movement and odd count updates happen implicitly.

✓ Subtracting countAtMost(k-1) from countAtMost(k) isolates subarrays with exactly k odd numbers.

This mathematical trick avoids enumerating all subarrays and is clearer when watching the two counts computed separately.

✓ Shrinking the window only happens when odd_count exceeds k, showing how the algorithm maintains a valid window at all times.

Seeing the left pointer move only when necessary clarifies the pruning step that keeps the window valid.

Practice

1. Consider the following Python function that counts the number of contiguous subarrays where the product of all elements is less than k. What is the returned value when calling numSubarrayProductLessThanK([10, 5, 2, 6], 100)?

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

easy

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Trace product and window boundaries

   Iterate right pointer: - right=0: product=10 <100, count=1 - right=1: product=50 <100, count=1+2=3 - right=2: product=100 ≥100, shrink window: product/=10=10, left=1, count=3+(2-1+1)=5 - right=3: product=10*6=60 <100, count=5+(3-1+1)=8

2. Step 2: Final count

   Total count is 8 valid subarrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected output 8 [OK]

Hint: Count increments by window size each iteration [OK]

Common Mistakes:

• Off-by-one in count increment
• Not shrinking window correctly

2. What is the time complexity of the optimal sliding window solution for the fruits problem, given an input array of length n? Assume fruit types are arbitrary integers but the number of distinct fruit types in the window is limited to two.

medium

A. O(n) because each element is visited at most twice by the two pointers

B. O(n log n) due to maintaining the hash map keys in sorted order

C. O(n²) because the inner while loop can run multiple times per outer iteration

D. O(n * k) where k is the number of distinct fruit types in the array

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window.

2. Step 2: Each element is added and removed at most once

   Thus total operations are proportional to 2n, which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hashmap is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to n²
• Thinking hashmap operations add log n
• Confusing distinct fruit count with input size

3. What is the time complexity of the optimal sliding window solution for the Grumpy Bookstore Owner problem when given an input array of length n and window size X?

medium

A. O(n)

B. O(n * X)

C. O(n + X)

D. O(n log n)

Solution

1. Step 1: Analyze outer loop

   The code iterates over the array once to compute base satisfaction (O(n)).

2. Step 2: Analyze sliding window loop

   The sliding window moves from start to end once, updating sums in O(1) per step, total O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

Hint: Sliding window updates in O(1) per step [OK]

Common Mistakes:

• Confusing with brute force O(n*X)
• Adding X to n instead of linear
• Assuming sorting needed

4. The following code attempts to find the length of the longest substring with at most k distinct characters. Identify the bug that causes incorrect results on some inputs.

from collections import OrderedDict

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0
    max_length = 0
    last_seen = OrderedDict()
    for right, char in enumerate(s):
        if char in last_seen:
            del last_seen[char]
        last_seen[char] = right
        max_length = max(max_length, right - left + 1)
        if len(last_seen) > k:
            _, idx = last_seen.popitem(last=False)
            left = idx + 1
    return max_length

medium

A. Not handling the case when k is zero or string is empty

B. Deleting the character from last_seen before re-inserting it

C. Updating max_length before shrinking the window when distinct chars exceed k

D. Using OrderedDict instead of a frequency map

Solution

1. Step 1: Locate max_length update position

   max_length is updated before shrinking the window when distinct chars exceed k, so invalid windows are counted.

2. Step 2: Understand impact

   This causes max_length to include substrings with more than k distinct characters, violating constraints.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving max_length update after shrinking fixes correctness [OK]

Hint: Update max_length only after ensuring window is valid [OK]

Common Mistakes:

• Updating max_length too early before shrinking window
• Confusing order of operations in sliding window

5. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the substring in s must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts and require window_count[c] >= t_count[c] for all c, same as original

B. Use brute force to check all substrings since counts no longer matter

C. Sort s and t and use two pointers to find minimal substring

D. Track only presence of characters from t in the window, increment have when a character appears at least once, decrement when it disappears

Solution

1. Step 1: Understand problem change

   Since counts do not matter, only presence of each character is required, so frequency counts can be replaced by boolean presence tracking.

2. Step 2: Modify sliding window logic

   Increment have when a character from t appears first time in window, decrement when it leaves. Shrink window when all characters are present.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking presence instead of counts solves the reuse variant efficiently [OK]

Hint: Track presence, not counts, when duplicates don't matter [OK]

Common Mistakes:

• Using original count-based logic
• Assuming brute force is needed
• Sorting breaks substring order