1248. Count Number Of Nice Subarrays

Problem Statement in English

You’re given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.

Approach

The solution to this is based on a class of problems that can be solved using the prefix sum technique. You can check out this post for a detailed explanation of the technique.

We maintain a count of odd numbers in the current prefix and store that in a hashmap. Whenever we encounter an odd number, we check to see how many times we have seen a prefix with odds - k odd numbers. The number of times we have seen that prefix is part of our answer for the current number. We add that to our result.

We also maintain a separate hashmap to store the count of even numbers in the current prefix, and we check that as well. This is because we can have prefixes that have odds - k odd numbers but different counts of even numbers, and those can also contribute to our answer.

So we check both hashmaps for the count of prefixes with odds - k odd numbers.

Don’t forget to increment the number of odd numbers in the current prefix and update the hashmaps before calculating the result for the current prefix.

And we’re done!

Solution in Python

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        odds = res = 0
        
        evenhm = defaultdict(int)
        hm = defaultdict(int)

        hm[0] = 1

        for num in nums:
            if num % 2:
                odds += 1
                hm[odds] += 1
            else:
                evenhm[odds] += 1

            diff = odds - k

            res += hm.get(diff, 0)
            res += evenhm.get(diff, 0)

        return res

Complexity

• Time: $O(n)$
  Since we traverse the array once.

• Space: $O(n)$
  Since we store the count of odd numbers in a hashmap.

And we are done.