Count Number of Nice Subarrays

medium sliding window counting

Problem

A "nice" subarray contains exactly k odd numbers. Given an array of integers and k, return the number of nice subarrays. Use atMost(k) − atMost(k−1) where atMost(k) counts subarrays with at most k odd numbers via a sliding window.

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

Output2

Nice subarrays: [1,1,2,1] and [1,2,1,1].

nums

def number_of_subarrays(nums, k):
    def at_most(t):
        if t < 0: return 0
        res = l = odds = 0
        for r, x in enumerate(nums):
            if x % 2: odds += 1
            while odds > t:
                if nums[l] % 2: odds -= 1
                l += 1
            res += r - l + 1
        return res
    return at_most(k) - at_most(k - 1)

function numberOfSubarrays(nums, k) {
  function atMost(t) {
    if (t < 0) return 0;
    let res = 0, l = 0, odds = 0;
    for (let r = 0; r < nums.length; r++) {
      if (nums[r] % 2) odds++;
      while (odds > t) {
        if (nums[l] % 2) odds--;
        l++;
      }
      res += r - l + 1;
    }
    return res;
  }
  return atMost(k) - atMost(k - 1);
}

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    private int atMost(int[] nums, int t) {
        if (t < 0) return 0;
        int res = 0, l = 0, odds = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] % 2 != 0) odds++;
            while (odds > t) {
                if (nums[l] % 2 != 0) odds--;
                l++;
            }
            res += r - l + 1;
        }
        return res;
    }
}

int atMost(vector<int>& nums, int t) {
    if (t < 0) return 0;
    int res = 0, l = 0, odds = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        if (nums[r] % 2) odds++;
        while (odds > t) {
            if (nums[l] % 2) odds--;
            l++;
        }
        res += r - l + 1;
    }
    return res;
}
int numberOfSubarrays(vector<int>& nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

Explanation

Counting subarrays with exactly k odd numbers is awkward directly, but there is a neat trick: exactly(k) = atMost(k) - atMost(k-1). Subarrays with at most k odds, minus those with at most k-1 odds, leaves precisely those with exactly k.

The helper atMost(t) uses a sliding window. We extend the right end r through the array, counting odd numbers in odds. Whenever odds exceeds t, we shrink from the left l until it is valid again.

The key counting line is res += r - l + 1. For each right end, every window starting between l and r is valid, and there are exactly r - l + 1 of them, so we add that many at once.

Example: nums = [1,1,2,1,1], k = 3. Computing atMost(3) and atMost(2) and subtracting gives 2, matching the nice subarrays [1,1,2,1] and [1,2,1,1].

Each element enters and leaves the window at most once across both passes, so the whole thing runs in linear time.

Time: O(n) Space: O(1)