Count Subarrays with K Odd Numbers

This is a very important sliding window + prefix counting problem

Problem Summary

In this problem, you are given:

An array arr[]
An integer k

Your task is to count:

The number of subarrays that contain exactly k odd numbers

In simple words, you need to find all continuous subarrays where the count of odd numbers is exactly equal to k. This is a very common problem in data structures and algorithms, especially in coding interviews and competitive programming.

Key Insight

A brute-force approach would check all possible subarrays, which takes O(n²) time. This is inefficient for large inputs.

To optimize this, we use a powerful technique:

At most k odds - at most (k-1) odds

This transforms the problem into a more efficient sliding window problem with O(n) time complexity.

Core Idea

The main idea is based on the formula:

exactly(k) = atMost(k) - atMost(k-1)

This means:

Count all subarrays having at most k odd numbers
Subtract all subarrays having at most (k-1) odd numbers

The result gives us subarrays having exactly k odd numbers.

Why this works?

This works because:

atMost(k) includes all subarrays with less than or equal to k odd numbers
atMost(k-1) includes all subarrays with less than or equal to (k-1) odd numbers
When we subtract them, we are left with only those subarrays that have exactly k odd numbers

This is a very important trick used in sliding window problems involving counting with constraints.

Function Idea

To implement this, we create a helper function:

atMost(k odds)

This function calculates the number of subarrays that contain at most k odd numbers using the sliding window technique.

Sliding Window Logic

We use a sliding window approach where we maintain:

A window that always contains at most k odd numbers
A left pointer and a right pointer

Steps involved:

Expand the window by moving the right pointer
Count odd numbers inside the window
If the number of odd elements exceeds k:
- Shrink the window by moving the left pointer
At each step, count valid subarrays using the formula:
- result += (right - left + 1)

This ensures we count all valid subarrays ending at the current index.

Java Solution

class Solution {

    // helper function: at most k odds
    private int atMost(int[] arr, int k) {

        int left = 0;
        int countOdd = 0;
        int result = 0;

        for (int right = 0; right < arr.length; right++) {

            if (arr[right] % 2 == 1) {
                countOdd++;
            }

            while (countOdd > k) {
                if (arr[left] % 2 == 1) {
                    countOdd--;
                }
                left++;
            }

            result += (right - left + 1);
        }

        return result;
    }

    public int countSubarrays(int[] arr, int k) {

        return atMost(arr, k) - atMost(arr, k - 1);
    }
}

Example Walkthrough

Input:

arr = [2, 5, 6, 9], k = 2

Now we find subarrays that contain exactly 2 odd numbers.

Valid subarrays are:

[2, 5, 6, 9]
[5, 6, 9]

Output:

This example shows how the sliding window efficiently identifies valid subarrays without checking all possibilities.

Complexity

Time Complexity: O(n)
- Each element is processed at most twice (once by right pointer and once by left pointer)
Space Complexity: O(1)
- No extra space is used apart from variables

Key Takeaways

Convert exact count problems into atMost problems for better efficiency
Use sliding window technique to avoid nested loops
Track only the required condition (here, odd numbers)
This is a very common and important interview pattern

Pattern Recognition

If you see problems like:

“count subarrays with exactly k elements”
“subarrays with constraints”
“odd/even conditions in subarrays”

You should think of:

Sliding Window + atMost(K) - atMost(K-1) technique

Summary

This problem demonstrates an optimized approach to count subarrays with exactly k odd numbers using the sliding window technique and prefix counting logic. Instead of checking all subarrays, we transform the problem using the atMost(k) - atMost(k-1) formula, which allows us to solve it efficiently in linear time. This technique is widely used in real-world applications and coding interviews where performance optimization is critical.