Count Number of Nice Subarrays
Asked at TikTok
Problem
Count Number of Nice Subarrays asks how many contiguous subarrays contain exactly k odd numbers. Replace each number with 1 if it is odd and 0 if it is even, and the problem becomes "count subarrays whose sum is exactly k" — a prefix-count classic.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Only parity matters. Map each element to x % 2, so the question is how many subarrays sum to k.
Prefix approach: keep odd, the number of odd values seen so far, and a count of how many prefixes had each odd count. A subarray ending here is nice iff an earlier prefix had exactly odd - k odd numbers.
Seed the counts with count[0] = 1 for the empty prefix.
Sliding-window alternative: exactly(k) = atMost(k) - atMost(k - 1), where atMost uses a standard shrinking window.
Walkthrough for [1,1,2,1,1], k = 3: odd prefix counts 0,1,2,2,3,4. Prefix 3 pairs with the one prefix of 0; prefix 4 pairs with the one prefix of 1. Answer 2.
Optimal Approach
Step 1: count = {0: 1}, odd = 0, res = 0.
Step 2: For each x:
odd += x % 2
res += count.get(odd - k, 0)
count[odd] += 1
Step 3: Return res.
Time: O(n). Space: O(n).
What Trips People Up in Real Interviews
A plain sliding window for "exactly k". A window cannot directly count exact matches because even numbers at the edges multiply the options — use prefix counts or the atMost trick.
Forgetting the empty-prefix seed.
Reading count[odd - k] with a negative index (Python wraps around silently). Guard with odd >= k.
Checking x % 2 == 1 on negative numbers in some languages — here inputs are positive, but mention it.
Solution Code
def numberOfSubarrays(nums, k):
count = [0] * (len(nums) + 1)
count[0] = 1
odd = res = 0
for x in nums:
odd += x % 2
if odd >= k:
res += count[odd - k]
count[odd] += 1
return resFrequently Asked Questions
What is the Count Number of Nice Subarrays problem?
Count Number of Nice Subarrays asks how many contiguous subarrays contain exactly `k` odd numbers. Replace each number with 1 if it is odd and 0 if it is even, and the problem becomes "count subarrays whose sum is exactly `k`" — a prefix-count classic.
How do you solve Count Number of Nice Subarrays?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Number of Nice Subarrays?
Count Number of Nice Subarrays is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Count Number of Nice Subarrays?
- A plain sliding window for "exactly k". A window cannot directly count exact matches because even numbers at the edges multiply the options — use prefix counts or the atMost trick.
- Forgetting the empty-prefix seed.
- Reading `count[odd - k]` with a negative index (Python wraps around silently). Guard with `odd >= k`.
- Checking `x % 2 == 1` on negative numbers in some languages — here inputs are positive, but mention it.