Count Number of Nice Subarrays

Count subarrays that contain exactly k odd numbers.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Count Number of Nice Subarrays: Count endings with at most 3 odds and at most 2 odds at every R, then subtract 14 - 12.

Input and goalCount subarrays that contain exactly `k` odd numbers.

Read the first odd at R = 0Both windows start at 0. Each has one valid ending at R, so totals become at_most(3) = 1 and at_most(2) = 1.

L<=3L<=2R1011221314

ranges<=3 [0..0]; <=2 [0..0]additions1 and 1totals1 and 1

Recognize it

Use it when subarrays must contain exactly k nonnegative events, while an at-most-k window can be repaired monotonically by moving its left boundary right.

Keep true

For each R, every start from L through R satisfies the relevant at-most limit, so that pass adds exactly R - L + 1 valid endings. The running total includes all right endpoints processed so far.

Reuse it

Convert exact monotone counts into at_most(k) - at_most(k - 1); at each right endpoint, the difference between the two valid-start ranges counts exactly-k subarrays ending there.

Pattern: Exact count from two sliding windows.

Simple idea: Counting exactly k can be hard. Count subarrays with at most k, then remove subarrays with at most k - 1.

exactly(k) = at_most(k) - at_most(k - 1)

def number_of_nice_subarrays(nums: list[int], odd_count: int) -> int:
   def at_most(limit: int) -> int:
      if limit < 0:
         return 0

      left = 0
      total = 0
      for right, num in enumerate(nums):
         limit -= num % 2
         while limit < 0:
            limit += nums[left] % 2
            left += 1
         total += right - left + 1
      return total

   return at_most(odd_count) - at_most(odd_count - 1)

Cost: $O(n)$ time and $O(1)$ space.