Data Structures and Algorithms (DSA)  

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:

2

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.

Membership not found