medium

Count Number of Nice Subarrays

Count subarrays that contain exactly k odd numbers.

1. Define the problem

Count Number of Nice Subarrays

Given an array of integers nums and an integer k, a subarray is called nice if it contains exactly k odd numbers . Return the number of nice subarrays. Count subarrays with at most k odd numbers, subtract the count with at most k minus one, and the difference is exactly k.

Constraints

  • 1 ≤ nums.length ≤ 5 × 104
  • 1 ≤ numsi ≤ 105
  • 0 ≤ k ≤ nums.length

Example

Inputnums = [1, 1, 2, 1, 1], k = 3
Output2

Explanation The two nice subarrays are [1,1,2,1] and [1,2,1,1], each containing exactly 3 odd numbers.

2. Visualize the solution

Count-at-most(k) minus count-at-most(k-1)

Count-at-most(k) minus count-at-most(k-1)
Statusgrow

Window [1,1,2,1] has 3 odd numbers <= 3; add 4 to the running count.

What happens in this step

atMost(3) — right=3, window [1,1,2,1] (left=0)
  odd values in window: 1, 1, 1 → oddCount = 3
  3 <= 3 → within limit, no shrinking
  count += (right - left + 1) = (3 - 0 + 1) = 4
Step 1 of 4

Steps to visualize

  1. Run a variable window that counts subarrays with at most a target number of odd values.
  2. Grow right and increment the odd counter when the new value is odd.
  3. While the odd counter exceeds the target, shrink from the left.
  4. At each right position, add the current window size to the count.
  5. Call this helper for k and for k minus one, then subtract.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count-at-most(k) minus count-at-most(k-1)
Statusgrow

Window [1,1,2,1] has 3 odd numbers <= 3; add 4 to the running count.

What happens in this step

atMost(3) — right=3, window [1,1,2,1] (left=0)
  odd values in window: 1, 1, 1 → oddCount = 3
  3 <= 3 → within limit, no shrinking
  count += (right - left + 1) = (3 - 0 + 1) = 4
Step 1 of 4
4. Solution

Solution

solution.tsTypeScript
function numberOfSubarrays(nums, k) {
  function atMost(limit) {
    if (limit < 0) return 0;
    let left = 0;
    let oddCount = 0;
    let count = 0;

    for (let right = 0; right < nums.length; right++) {
      if (nums[right] % 2 !== 0) oddCount++;

      while (oddCount > limit) {
        if (nums[left] % 2 !== 0) oddCount--;
        left++;
      }

      count += right - left + 1;
    }

    return count;
  }

  return atMost(k) - atMost(k - 1);
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
nums = [1, 1, 2, 1, 1], k = 32Docstring example
nums = [2, 4, 6], k = 06k = 0 counts every run of pure evens
nums = [1, 3, 5], k = 22All odd numbers
nums = [2, 4, 6], k = 10k larger than the total odd count
nums = [1], k = 11Single odd element
nums = [1, 1, 1], k = 13Every single-element window qualifies
nums = [2, 1, 2, 1, 2], k = 24Mixed evens and odds with multiple valid windows

Keep reading

TopicDescription
Sliding WindowSolve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides.
Maximum Average Subarray IFind the contiguous subarray of a fixed length with the largest average.
Longest Substring Without Repeating CharactersFind the length of the longest run of characters in a string with no repeats.
Permutation in StringCheck whether one string contains a rearrangement of another string as a substring.
Minimum Size Subarray SumFind the shortest contiguous subarray whose sum is at least a target value.
Longest Repeating Character ReplacementFind the longest substring you can turn into one repeated letter with a limited number of swaps.