Count Number of Nice Subarrays (Exactly K Odd Numbers)

Problem

Given an array of integers and an integer k, count the number of contiguous subarrays containing exactly k odd numbers.

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

Python Solution

def number_of_subarrays(nums, k):
    def at_most(target):
        if target < 0:
            return 0
        left = 0
        odd_count = 0
        count = 0
        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                odd_count += 1
            while odd_count > target:
                if nums[left] % 2 == 1:
                    odd_count -= 1
                left += 1
            count += right - left + 1
        return count

    return at_most(k) - at_most(k - 1)

C++ Solution

int atMostOdd(vector<int>& nums, int target) {
    if (target < 0) return 0;
    int left = 0, oddCount = 0, count = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] % 2 == 1) oddCount++;
        while (oddCount > target) {
            if (nums[left] % 2 == 1) oddCount--;
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int numberOfSubarrays(vector<int>& nums, int k) {
    return atMostOdd(nums, k) - atMostOdd(nums, k - 1);
}

Java Solution

class Solution {
    private int atMostOdd(int[] nums, int target) {
        if (target < 0) return 0;
        int left = 0, oddCount = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 == 1) oddCount++;
            while (oddCount > target) {
                if (nums[left] % 2 == 1) oddCount--;
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }

    public int numberOfSubarrays(int[] nums, int k) {
        return atMostOdd(nums, k) - atMostOdd(nums, k - 1);
    }
}

Complexity

Time: O(n) — two linear sliding-window passes. Space: O(1) — only a running odd-count and pointers. Same atMost(K) - atMost(K-1) pattern as Binary Subarrays With Sum, applied to counting odd numbers instead of summing.