Count Number of Nice Subarrays - Sliding Window - Visualization

Given an integer array nums and an integer k, return the number of nice subarrays.

A nice subarray is a contiguous subarray that contains exactly k odd numbers.

Example:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The nice subarrays are [1,1,2,1] and [1,2,1,1].

Understanding the Problem

We are given an integer array nums and an integer k. Our goal is to count how many contiguous subarrays (or continuous slices of the array) have exactly k odd numbers.

These subarrays are called nice subarrays.

For example:

Input: nums = [1, 1, 2, 1, 1], k = 3  
Output: 2

Nice subarrays with exactly 3 odd numbers: [1, 1, 2, 1] and [1, 2, 1, 1].

Step-by-Step Solution with Example

Step 1: Reframe the Problem

Instead of directly counting subarrays with exactly k odd numbers, we count:

• Subarrays with at most k odd numbers
• Subarrays with at most k-1 odd numbers

The number of subarrays with exactly k odd numbers is the difference:

exactlyK(k) = atMost(k) - atMost(k - 1)

Step 2: Understand the Helper Function atMost(k)

This function counts how many subarrays have at most k odd numbers using the sliding window approach.

• We use two pointers: left and right.
• We move the right pointer one step at a time and track the number of odd numbers in the current window.
• If the count of odd numbers exceeds k, we move the left pointer to shrink the window.
• At every step, we add right - left + 1 to the result because that’s how many valid subarrays end at right.

Step 3: Walk Through the Example [1, 1, 2, 1, 1] with k = 3

Let’s compute atMost(3) first:

• right = 0, num = 1 → oddCount = 1, subarrays = 1
• right = 1, num = 1 → oddCount = 2, subarrays = 3
• right = 2, num = 2 → even, oddCount = 2, subarrays = 6
• right = 3, num = 1 → oddCount = 3, subarrays = 10
• right = 4, num = 1 → oddCount = 4 → exceed k → move left to reduce oddCount = 3 → subarrays = 14

So, atMost(3) = 14

Now compute atMost(2) using similar steps and you’ll get 12.

Final count = 14 - 12 = 2, which matches our expected output.

Step 4: Implement in Code

def numberOfSubarrays(nums, k):
    def atMost(k):
        left = 0
        count = 0
        oddCount = 0

        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                oddCount += 1
            while oddCount > k:
                if nums[left] % 2 == 1:
                    oddCount -= 1
                left += 1
            count += right - left + 1
        return count

    return atMost(k) - atMost(k - 1)

Edge Cases

• All even numbers: If nums contains no odd numbers, the answer will be 0 unless k == 0.
• All odd numbers: Can form many nice subarrays. Be careful with boundaries and window resizing.
• Empty array: Should return 0 safely.
• k greater than total odd numbers: No subarray can satisfy, so answer is 0.

Final Thoughts

This problem becomes manageable by converting the exact count question into a more flexible "at most" count using the sliding window technique. It’s an elegant way to reduce complexity and helps you gain insight into how prefix counts and window shrinking work together.

By following the logic carefully and considering all edge cases, beginners can confidently solve such array problems using two-pointer strategies.

1. Define a helper function atMost(k) that returns the count of subarrays with at most k odd numbers.
2. Use a sliding window with two pointers left and right.
3. Keep a counter oddCount to track the number of odd numbers in the current window.
4. Initialize a result counter res = 0.
5. Traverse the array with the right pointer:
6. → If nums[right] is odd, decrement k (or increment oddCount).
7. → While oddCount > k, move the left pointer forward and adjust oddCount if needed.
8. → For each right, add (right - left + 1) to the result, which represents subarrays ending at right.
9. Finally, return atMost(k) - atMost(k-1) to get the count of subarrays with exactly k odd numbers.

O(1)

Explanation: The algorithm uses a constant amount of extra space for variables like left, right, oddCount, and result counters. No additional data structures are used, making the space complexity constant.