Problem Statement

Count Number of Nice Subarrays

You are given a list of whole numbers called nums and a number k. A subarray is just a chunk of the list that sits next to each other, with no gaps. We call a subarray "nice" if it holds exactly k odd numbers. Your job is to count how many nice subarrays there are. Counting "exactly k" directly is fiddly, so we use a clever shortcut. Think of it like measuring water. If you want the amount between the 2 liter and 3 liter marks, you take "everything up to 3 liters" and subtract "everything up to 2 liters." Here we do the same with a trick called exactly(k) = atMost(k) - atMost(k-1). The word atMost(k) means "count of subarrays that have k odd numbers or fewer." Subtract the ones with too few, and what is left is exactly k. To count "at most k," we use a sliding window, which is a stretchy frame over the list that we grow on the right and shrink on the left to keep it valid.

mediumSliding WindowSliding WindowTime: O(n) · Space: O(1)

Signals to notice

count subarrays with exactly k odd numbersexact = atMost(k) - atMost(k-1)same trick as subarrays with k different integers

Brute force first

Check every subarray — O(n²).

The key insight

exactly(k) = atMost(k) - atMost(k-1). atMost(k): sliding window counting subarrays with ≤ k odd numbers. O(n).

Trace it on `nums=[1,1,2,1,1], k=3`

Goal: answer = atMost(3) - atMost(2). Odd values are the 1s at indices 0,1,3,4.
atMost(3): r=0(1) odd=1, r=1(1) odd=2, r=2(2) odd=2 -> result grows 1,3,6 (window [0..r])
atMost(3): r=3(1) odd=3 ok, result += 4 -> 10; r=4(1) odd=4>3, shrink left to 1 (odd=3), result += 4 -> 14
atMost(3) = 14
atMost(2): r=0 odd=1, r=1 odd=2, r=2 odd=2 -> result 1,3,6 (no shrink yet)
atMost(2): r=3(1) odd=3>2, shrink left->1 (odd=2), result += 3 -> 9
atMost(2): r=4(1) odd=3>2, shrink left->2 (odd=2), result += 3 -> 12; atMost(2) = 12
answer = atMost(3) - atMost(2) = 14 - 12 = 2

What must stay true

Replace 'odd' with a counter. atMost(k) counts subarrays with ≤ k odds using the standard window technique. Subtraction gives exactly k.

Shape of the loop

function atMost(k):
  left = 0; odd = 0; result = 0
  for right in 0..n-1:
    if nums[right] is odd: odd += 1
    while odd > k:
      if nums[left] is odd: odd -= 1
      left += 1
    result += right - left + 1
  return result
answer = atMost(k) - atMost(k-1)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Same as Subarrays with K Different Integers — direct 'exactly k' counting is hard, but the subtraction trick makes it easy.

Sliding Window Pattern