Medium

Count Number of Nice Subarrays

047

Return the number of contiguous subarrays containing exactly k odd numbers.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    1,
    2,
    1,
    1
  ],
  "k": 3
}

Output
2

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

The interesting point here is that we can make a simple transformation of nums to a boolean array indicating the parity of each element. Then a sum equal to k means a subarray with k odd elements.

Reveal reference solution +

pythonREFERENCE

def numberOfSubarrays(self, nums: List[int], k: int) -> int:
    # Transform: each number = 0 if even, 1 if odd
    nums = [num % 2 for num in nums]
    return self.subarraySum(nums, k)

def subarraySum(self, nums: List[int], k: int) -> int:
    prev_sum = Counter({0:1})
    n, prefix_sum, res = len(nums), 0, 0

    for i in range(n):
        prefix_sum += nums[i]
        if prefix_sum - k in prev_sum:
            res += prev_sum[prefix_sum - k]
        prev_sum[prefix_sum] += 1

    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗