Count Subarray with k odds

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Count subarrays with exactly k odd numbers. Prefix sum with at-most-k trick.

Algorithm

1Count(exactly k) = Count(at most k) - Count(at most k-1). Count at most k: sliding window.

Common Pitfalls

•Same as LC 1248. Sliding window counts at-most-k. Subtract to get exactly-k. O(n).

Count Subarray with k odds.java

Java

// Approach: Sliding window: count subarrays with at most k odds minus subarrays with at most k-1 odds.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int countSubarrays(int[] arr, int k) {
        LinkedList<Integer> lt = new LinkedList<>();
        int pr = -1, ans = 0, n = arr.length;
        for (int i = 0; i <= n; i++) {
            if (i == n || arr[i] % 2 == 1) {
                if (lt.size() == k) {
                    int f = lt.getFirst() - pr;
                    int s = i - lt.getLast();
                    ans += f * s;
                    pr = lt.removeFirst();
                }
                lt.add(i);
            }
        }
        
        return ans;
    }
}

Was this solution helpful?