Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count Number of Nice Subarrays

MEDIUMProblemSolveExternal Links

Description

Given an array of integers nums and an integer k, a continuous subarray is called nice if it contains exactly k odd numbers.

Return the number of nice sub-arrays.

A subarray is a contiguous, non-empty sequence of elements within the array. For example, in [1, 2, 3], the subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Note that elements can be any positive integer — what matters is only whether each element is odd or even. So this problem is fundamentally about counting contiguous segments that contain a specific number of odd values.

Examples

Example 1

Input: nums = [1, 1, 2, 1, 1], k = 3

Output: 2

Explanation: We need subarrays containing exactly 3 odd numbers. The odd elements are at indices 0, 1, 3, and 4 (values 1, 1, 1, 1). The element at index 2 (value 2) is even.

The two valid subarrays are:

  • [1, 1, 2, 1] from index 0 to 3: contains odds at indices 0, 1, 3 → 3 odd numbers ✓
  • [1, 2, 1, 1] from index 1 to 4: contains odds at indices 1, 3, 4 → 3 odd numbers ✓

No other subarray has exactly 3 odd numbers.

Example 2

Input: nums = [2, 4, 6], k = 1

Output: 0

Explanation: All elements are even — there are no odd numbers in the array at all. Since k = 1 requires at least one odd number, no subarray can be nice. The answer is 0.

This is an important edge case: when the array has fewer odd numbers than k, the answer is always 0.

Example 3

Input: nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], k = 2

Output: 16

Explanation: The odd numbers are at indices 3 and 6 (both have value 1). Every nice subarray must include both of these odd elements.

The left boundary can start at any of indices 0, 1, 2, or 3 (4 choices — anywhere from the beginning up to and including the first odd number). The right boundary can end at any of indices 6, 7, 8, or 9 (4 choices — from the second odd number to the end). So the total count is 4 × 4 = 16.

This example illustrates a key pattern: even numbers surrounding the required odd numbers act as "flexible padding" that multiplies the number of valid subarrays.

Constraints

  • 1 ≤ nums.length ≤ 50,000
  • 1 ≤ nums[i] ≤ 10^5
  • 1 ≤ k ≤ nums.length

Editorial

Brute Force

Intuition

The simplest approach is to consider every possible contiguous subarray, count the odd numbers within it, and check if that count equals k.

Imagine you have a line of people, and each person is wearing either a red shirt (odd number) or a blue shirt (even number). You want to count how many groups of consecutive people have exactly k red shirts. The brute force way is to pick every possible starting person, then extend the group one person at a time to the right, keeping a running count of red shirts. Every time the count hits exactly k, you have found a nice group.

We maintain a running odd count as we extend the subarray, so each extension is O(1). But we check all O(n²) starting-ending pairs, making this O(n²) overall.

Step-by-Step Explanation

Let's trace through nums = [1, 1, 2, 1, 1], k = 3:

Step 1: Initialize count = 0. Start outer loop with i = 0.

Step 2: i = 0, j = 0: element is 1 (odd). odd_count = 1. Is 1 == 3? No.

Step 3: i = 0, j = 1: element is 1 (odd). odd_count = 2. Is 2 == 3? No.

Step 4: i = 0, j = 2: element is 2 (even). odd_count stays 2. Is 2 == 3? No. Even numbers don't change the odd count.

Step 5: i = 0, j = 3: element is 1 (odd). odd_count = 3. Is 3 == 3? Yes! count = 1. Subarray [1, 1, 2, 1].

Step 6: i = 0, j = 4: element is 1 (odd). odd_count = 4. Is 4 == 3? No. We overshot — too many odd numbers.

Step 7: Move to i = 1, reset odd_count = 0. j = 1: odd_count = 1 (1 is odd). j = 2: odd_count = 1 (2 is even). j = 3: odd_count = 2 (1 is odd).

Step 8: i = 1, j = 4: element is 1 (odd). odd_count = 3. Is 3 == 3? Yes! count = 2. Subarray [1, 2, 1, 1].

Step 9: Move to i = 2. j = 2: odd_count = 0. j = 3: odd_count = 1. j = 4: odd_count = 2. Maximum is 2 < 3, no match.

Step 10: i = 3 and i = 4 have at most 2 and 1 odd numbers respectively. No matches.

Result: count = 2.

Brute Force — Checking All Subarrays for Odd Count — Watch how we fix a starting index, extend rightward, and maintain a running count of odd numbers. When the count reaches exactly k, we found a nice subarray.

Algorithm

  1. Initialize count = 0
  2. For each starting index i from 0 to n - 1:
    • Initialize odd_count = 0
    • For each ending index j from i to n - 1:
      • If nums[j] is odd, increment odd_count
      • If odd_count == k, increment count
  3. Return count

Code

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int oddCount = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] % 2 == 1) {
                    oddCount++;
                }
                if (oddCount == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
};
class Solution:
    def numberOfSubarrays(self, nums: list[int], k: int) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n):
            odd_count = 0
            for j in range(i, n):
                if nums[j] % 2 == 1:
                    odd_count += 1
                if odd_count == k:
                    count += 1
        
        return count
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int oddCount = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] % 2 == 1) {
                    oddCount++;
                }
                if (oddCount == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. For each starting index, the inner loop runs up to n times. We examine roughly n × (n + 1) / 2 subarrays total. Each check is O(1) since we maintain a running odd count. With n up to 50,000, this means up to ~1.25 × 10^9 operations — far too slow.

Space Complexity: O(1)

We only use a few integer variables (count, odd_count, i, j). No extra data structures.

Why This Approach Is Not Efficient

With n up to 50,000, the brute force generates approximately 1.25 × 10^9 operations — well beyond the typical time limit. The core problem is redundant work: when we shift the starting index from i to i + 1, we discard all the odd-count information we accumulated and start from scratch.

Key insight — Parity Reduction: Notice that the actual values of the numbers don't matter — only whether each number is odd or even. If we replace every element with its parity (odd → 1, even → 0), the problem transforms into: count subarrays with sum exactly k in a binary array. This is the classic "Subarray Sum Equals K" problem.

With this transformation, we can use a prefix sum + hash map approach to solve the problem in O(n) time. For each position, the prefix sum tells us how many odd numbers we've seen from the start. If the current prefix sum minus the prefix sum at some earlier position equals k, then the subarray between those positions has exactly k odd numbers.

Better Approach - Prefix Sum with Hash Map

Intuition

First, convert the problem: replace each element with its parity (1 if odd, 0 if even). Now we need to count subarrays whose elements sum to exactly k — which is the classic prefix sum problem.

Maintain a running prefix sum that counts how many odd numbers we've seen so far. At each position j, we ask: "How many earlier positions i had a prefix sum of (current_prefix − k)?" If such a position exists, then the subarray from i+1 to j contains exactly k odd numbers.

A hash map stores the frequency of each prefix sum value we've encountered. Looking up the answer for each position is O(1).

Think of it as keeping a running tally of odd numbers seen. If you've seen 5 odd numbers total by position j, and you need exactly 3 in a subarray ending here, you need a previous position where the tally was 5 − 3 = 2. The hash map tells you instantly how many such positions exist.

Step-by-Step Explanation

Let's trace through nums = [1, 1, 2, 1, 1], k = 3:

First, compute parity: [1, 1, 0, 1, 1] (odd→1, even→0).

Step 1: Initialize: prefixSum = 0, count = 0, map = {0: 1}. The entry {0: 1} represents the empty prefix — zero odd numbers seen before processing any element.

Step 2: Process index 0: nums[0] = 1 (odd). prefixSum = 0 + 1 = 1. Look up (1 − 3) = −2 in map. Not found — we can't have seen a negative prefix sum. Store prefixSum: map = {0: 1, 1: 1}.

Step 3: Process index 1: nums[1] = 1 (odd). prefixSum = 1 + 1 = 2. Look up (2 − 3) = −1. Not found. Store: map = {0: 1, 1: 1, 2: 1}.

Step 4: Process index 2: nums[2] = 2 (even). prefixSum = 2 + 0 = 2. Look up (2 − 3) = −1. Not found. Update frequency of 2: map = {0: 1, 1: 1, 2: 2}.

Step 5: Process index 3: nums[3] = 1 (odd). prefixSum = 2 + 1 = 3. Look up (3 − 3) = 0. Found with frequency 1! One subarray ending at index 3 has exactly 3 odd numbers: [1, 1, 2, 1] (from start to index 3). count = 0 + 1 = 1. Store: map = {0: 1, 1: 1, 2: 2, 3: 1}.

Step 6: Process index 4: nums[4] = 1 (odd). prefixSum = 3 + 1 = 4. Look up (4 − 3) = 1. Found with frequency 1! One subarray ending at index 4 has exactly 3 odd numbers: [1, 2, 1, 1] (from index 1 to 4). count = 1 + 1 = 2.

Result: count = 2.

Prefix Sum + Hash Map — Counting Nice Subarrays — Watch how we maintain a running count of odd numbers (prefix sum of parities) and use a hash map to instantly find how many earlier positions differ by exactly k.

Algorithm

  1. Initialize a hash map prefixCount with {0: 1}
  2. Initialize prefixSum = 0 and count = 0
  3. For each element nums[i]:
    • Add nums[i] % 2 to prefixSum (1 if odd, 0 if even)
    • Compute complement = prefixSum - k
    • If complement exists in prefixCount, add prefixCount[complement] to count
    • Increment prefixCount[prefixSum] by 1
  4. Return count

Code

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1;
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num % 2;
            int complement = prefixSum - k;
            if (prefixCount.count(complement)) {
                count += prefixCount[complement];
            }
            prefixCount[prefixSum]++;
        }
        
        return count;
    }
};
class Solution:
    def numberOfSubarrays(self, nums: list[int], k: int) -> int:
        prefix_count = {0: 1}
        prefix_sum = 0
        count = 0
        
        for num in nums:
            prefix_sum += num % 2
            complement = prefix_sum - k
            if complement in prefix_count:
                count += prefix_count[complement]
            prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
        
        return count
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1);
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num % 2;
            int complement = prefixSum - k;
            if (prefixCount.containsKey(complement)) {
                count += prefixCount.get(complement);
            }
            prefixCount.put(prefixSum, prefixCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once. At each step, computing the parity (num % 2) is O(1), the hash map lookup is O(1) on average, and the hash map insertion is O(1) on average. Total: n × O(1) = O(n).

Space Complexity: O(n)

In the worst case, every prefix sum is unique (e.g., an array of all odd numbers gives prefix sums 1, 2, 3, ..., n), so the hash map stores up to n + 1 entries. This is O(n) extra space.

Why This Approach Is Not Efficient

The prefix sum + hash map approach achieves optimal O(n) time complexity, but uses O(n) extra space for the hash map. While this is perfectly acceptable for the given constraints, we can improve the space complexity.

The critical observation is that after the parity transformation (odd → 1, even → 0), our array becomes binary — containing only 0s and 1s. Binary arrays have a special property: the running sum is monotonically non-decreasing. Adding any element either increases the sum by 1 (if odd) or leaves it unchanged (if even). It never decreases.

This monotonic behavior means a sliding window approach works perfectly. When the window sum exceeds our target, we can always fix it by shrinking from the left — the sum will never increase when we remove elements. This predictability enables an O(1) space solution using the atMost(k) - atMost(k-1) trick.

Optimal Approach - Sliding Window

Intuition

Counting subarrays with exactly k odd numbers directly via a sliding window is hard because the window can be nice at multiple sizes (due to even-number padding). The key decomposition is:

exactly(k) = atMost(k) − atMost(k − 1)

The helper function atMost(k) counts subarrays with at most k odd numbers. This is a classic sliding window: expand the right end, and whenever the odd count exceeds k, shrink from the left until it's within bounds again. At each right position, the number of valid subarrays ending there is (right − left + 1).

By subtracting atMost(k − 1) from atMost(k), we remove all subarrays with 0, 1, 2, ..., (k−1) odd numbers, leaving only those with exactly k.

This works because the parity values are non-negative (0 or 1), so the odd count in any window only grows when we expand and only shrinks when we contract — making the sliding window invariant reliable.

Step-by-Step Explanation

Let's trace through nums = [1, 1, 2, 1, 1], k = 3.

Parity: [1, 1, 0, 1, 1].

--- Computing atMost(3) ---

Step 1: Initialize left = 0, oddSum = 0, total = 0.

Step 2: right = 0: nums[0] = 1 (odd), oddSum = 1. 1 ≤ 3? Yes. Subarrays ending at 0: [1]. Contribute 0 − 0 + 1 = 1. total = 1.

Step 3: right = 1: nums[1] = 1 (odd), oddSum = 2. 2 ≤ 3? Yes. Contribute 2. total = 3.

Step 4: right = 2: nums[2] = 2 (even), oddSum = 2. 2 ≤ 3? Yes. Contribute 3. total = 6.

Step 5: right = 3: nums[3] = 1 (odd), oddSum = 3. 3 ≤ 3? Yes. Contribute 4. total = 10.

Step 6: right = 4: nums[4] = 1 (odd), oddSum = 4. 4 ≤ 3? No! Shrink: remove nums[0] (odd), left = 1, oddSum = 3. 3 ≤ 3? Yes. Contribute 4 − 1 + 1 = 4. total = 14.

atMost(3) = 14

--- Computing atMost(2) ---

Step 7: Reset: left = 0, oddSum = 0, total = 0.

Step 8: right = 0: oddSum = 1. 1 ≤ 2? Yes. Contribute 1. total = 1.
right = 1: oddSum = 2. 2 ≤ 2? Yes. Contribute 2. total = 3.

Step 9: right = 2: oddSum = 2 (even, no change). Contribute 3. total = 6.

Step 10: right = 3: oddSum = 3. 3 ≤ 2? No! Shrink: remove nums[0] (odd), left = 1, oddSum = 2. Contribute 3 − 1 + 1 = 3. total = 9.

Step 11: right = 4: oddSum = 3. 3 ≤ 2? No! Shrink: remove nums[1] (odd), left = 2, oddSum = 2. Contribute 4 − 2 + 1 = 3. total = 12.

atMost(2) = 12

Result: exactly(3) = atMost(3) − atMost(2) = 14 − 12 = 2.

Sliding Window — atMost(k) Two-Pass Counting — Watch how the sliding window expands rightward, counting odd numbers, and shrinks from the left when the odd count exceeds the limit. Two passes with different limits give us the exact count.

Algorithm

  1. Define a helper function atMost(k):
    • If k < 0, return 0
    • Initialize left = 0, oddSum = 0, count = 0
    • For each right from 0 to n − 1:
      • If nums[right] is odd, increment oddSum
      • While oddSum > k: if nums[left] is odd, decrement oddSum; increment left
      • Add (right − left + 1) to count
    • Return count
  2. Return atMost(k) − atMost(k − 1)

Code

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
private:
    int atMost(vector<int>& nums, int k) {
        if (k < 0) return 0;
        
        int left = 0, oddSum = 0, count = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            oddSum += nums[right] % 2;
            while (oddSum > k) {
                oddSum -= nums[left] % 2;
                left++;
            }
            count += right - left + 1;
        }
        
        return count;
    }
};
class Solution:
    def numberOfSubarrays(self, nums: list[int], k: int) -> int:
        def at_most(limit: int) -> int:
            if limit < 0:
                return 0
            
            left = 0
            odd_sum = 0
            count = 0
            
            for right in range(len(nums)):
                odd_sum += nums[right] % 2
                while odd_sum > limit:
                    odd_sum -= nums[left] % 2
                    left += 1
                count += right - left + 1
            
            return count
        
        return at_most(k) - at_most(k - 1)
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    private int atMost(int[] nums, int k) {
        if (k < 0) return 0;
        
        int left = 0, oddSum = 0, count = 0;
        
        for (int right = 0; right < nums.length; right++) {
            oddSum += nums[right] % 2;
            while (oddSum > k) {
                oddSum -= nums[left] % 2;
                left++;
            }
            count += right - left + 1;
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We call atMost twice, each doing a single pass. In each pass, the right pointer advances n times and the left pointer also advances at most n times total (each element is removed at most once). So each pass is O(n), and two passes give O(2n) = O(n).

Space Complexity: O(1)

We use only a constant number of variables: left, oddSum, count, and right. No hash map, no auxiliary array. This is the key advantage over the prefix sum approach — we eliminated the O(n) hash map by exploiting the non-negative (binary parity) structure of the problem.