MediumArrayHash TableMathSliding WindowPrefix SumUpdated Sep 2026

1248. Count Number of Nice Subarrays

Asked at TikTok

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an integer array nums and an integer k. A subarray is a contiguous block of the array — you take a start index and an end index and keep everything in between.

A subarray is called nice if it contains exactly k odd numbers. Even numbers inside it do not matter at all; only how many odd values it holds.

Return the number of nice subarrays (not the subarrays themselves, just how many there are).

Only parity matters

nums1121101234The even value 2 contributes nothing to the odd countparitysum 3sum 31101101234Two windows sum to 3, so the answer is 2
Replace each value by 1 if odd and 0 if even, then count blocks whose sum is exactly k = 3.

Constraints

  • ●1 <= nums.length <= 50000
  • ●1 <= nums[i] <= 10^5
  • ●1 <= k <= nums.length

Examples

Example 1
Inputnums = [1,1,2,1,1], k = 3
Output2
WhyOnly two blocks have exactly 3 odd numbers: indices 0..3 ([1,1,2,1]) and indices 1..4 ([1,2,1,1]). Every other block has 2 or 4 odd numbers.
Example 2
Inputnums = [2,4,6], k = 1
Output0
WhyAll values are even, so no subarray can ever contain an odd number. The count is 0.
Example 3
Inputnums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output16
WhyThe two odd numbers are at indices 3 and 6. A subarray is nice when it covers both of them but no others, giving 4 choices of left end times 4 choices of right end = 16.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Only parity matters. Map each element to x % 2, so the question is how many subarrays sum to k.

2

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.

3

Seed the counts with count[0] = 1 for the empty prefix.

4

Sliding-window alternative: exactly(k) = atMost(k) - atMost(k - 1), where atMost uses a standard shrinking window.

5

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).

Prefix odd-counts

nums1121101234iStep 1 — walking left to right, odd counts so far are0,1,2,2,3,4count01234seen11111Step 2 — at odd = 3 we add count[0] = 1; at odd = 4 weadd count[1] = 1res += count[odd − k]count[odd] += 1answer = 1 + 1 = 2
A subarray ending here is nice when an earlier prefix had exactly odd − k odd numbers.
ComplexityTime O(n)Space O(n)One pass over the array; the hash map holds at most n+1 distinct prefix odd-counts.

What Trips People Up in Real Interviews

1

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.

2

Forgetting the empty-prefix seed.

3

Reading count[odd - k] with a negative index (Python wraps around silently). Guard with odd >= k.

4

Checking x % 2 == 1 on negative numbers in some languages — here inputs are positive, but mention it.

Solution Code

O(n) time
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 res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.