Count Number of Nice Subarrays

Count Number of Nice Subarrays

What is this problem about?

An array is considered "nice" if it contains exactly $k$ odd numbers. You are given an array of integers and an integer $k$, and your task is to find the total number of continuous subarrays that are nice. This is a classic subarray counting problem where the condition depends on a specific property (parity) of the elements.

Why is this asked in interviews?

This problem is a staple at companies like Microsoft, Amazon, and TikTok because it tests the ability to transform a data stream. By replacing all odd numbers with 1 and all even numbers with 0, the problem becomes "Find the number of subarrays with a sum equal to $k$." This transformation reveals whether a candidate can simplify a problem to a known pattern.

Algorithmic pattern used

This problem is typically solved using the Sliding Window pattern or the Prefix Sum with Hash Table pattern.

1. Sliding Window: Find the number of subarrays with at most $k$ odd numbers and subtract the number of subarrays with at most $k-1$ odd numbers.
2. Prefix Sum: Maintain a running count of odd numbers encountered. Store the frequency of each prefix count in a Hash Map. For a current prefix count $S$, any previous prefix count equal to $S - k$ forms a valid "nice" subarray.

Example explanation

Array: [1, 1, 2, 1, 1], $k = 3$.

• Mapping to 0s and 1s: [1, 1, 0, 1, 1].
• Prefix Sums: 0, 1, 2, 2, 3, 4.
• Count frequency: {0:1, 1:1, 2:2, 3:1, 4:1}.
• When prefix sum is 3: Check frequency of $3-3=0$. Freq(0) is 1. (Subarray [1, 1, 2, 1]).
• When prefix sum is 4: Check frequency of $4-3=1$. Freq(1) is 1. (Subarray [1, 2, 1, 1]). Total: 2.

Common mistakes candidates make

The most common mistake is using a naive $O(n^2)$ approach to check every subarray, which will fail for large inputs. Another is failing to handle the "at most $k$" logic correctly if using the sliding window approach. Some candidates also forget to include the initial prefix sum of 0 in their frequency map.

Interview preparation tip

Whenever a problem asks for "subarrays with exactly $k$ properties," think about the "AtMost(k) - AtMost(k-1)" trick. It’s a powerful way to use sliding window logic for "exactly" constraints which are otherwise hard to track with two pointers.