Count Number of Nice Subarrays - Solution & Explanation

Problem Overview: You are given an integer array and an integer k. A subarray is considered nice if it contains exactly k odd numbers. The goal is to count how many such subarrays exist. Since subarrays are contiguous, the solution relies on efficiently tracking odd-number counts while scanning the array.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

The straightforward method checks every possible subarray. Start from each index i, extend the subarray to the right, and keep a running count of odd numbers. Every time the odd count equals k, increment the answer. If the count exceeds k, you can stop extending that subarray because additional elements will only increase the count further. This approach uses simple iteration and parity checks (num % 2) without extra data structures. While easy to implement, the nested iteration leads to O(n²) time complexity, which becomes slow for large arrays.

Approach 2: Two-Pointer / Sliding Window (O(n) time, O(1) space)

The optimal approach uses the sliding window technique to count subarrays with at most k odd numbers. If you can compute the number of subarrays with at most k odds and subtract the number with at most k-1 odds, the result equals the number with exactly k odds. Maintain two pointers (left and right) while scanning the array. Expand the window by moving right, update the odd count, and shrink from the left whenever the count exceeds k. For each valid window, add right - left + 1 to the result because all subarrays ending at right and starting within the window are valid.

This works because the window always maintains the constraint of at most k odd numbers. Each element enters and leaves the window at most once, giving a linear scan. The approach effectively converts a counting problem into a window expansion problem, which is a common pattern in sliding window and prefix sum-style problems.

Recommended for interviews: Interviewers typically expect the O(n) sliding window solution. It shows you understand how to transform “exactly k” constraints into two “at most k” computations and manage dynamic windows efficiently. The brute force approach demonstrates baseline reasoning about subarrays, but the two-pointer optimization shows stronger algorithmic insight and familiarity with common hash table and window-counting patterns used in array problems.