Problem description:

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

1
2
3
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:

1
2
3
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:

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

Solution:

Sliding window

  1. left right boundary to count if nums[i:j] have k odd numbers
  2. start to count the number of subarray and moving left pointer i
  3. notice we end the while loop and move i to the next number. The count would rollover to next round when j increase because if nums[j] is even, then it would create more combinations based on previous.
1
2
3
4
5
6
7
8
9
10
11
nums: [0,1,0,0,1], k = 1
[0,1]
[1] - i move to nums[1], exiting while loop, count = 2
then we start to move j
[0,1,0] 
[0,1,0,0]
[1,0]
[1,0,0]
[0,0,1]
[0,1]
[1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # sliding window
        # start to count when having k odd numbers in subarray
        i = res = count = 0
        for j in range(len(nums)):
            if nums[j] & 1:
                k -= 1
                count = 0
            
            while k == 0:
                k += nums[i] & 1
                i += 1
                count += 1
            res += count
        return res

Replace even elements with 0 and odd elements with 1.

The problem is then reduced to the number of subarrays with sum k.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # mod number to 2, change the question to subarray sum to k
        cur_sum = res = 0
        dic = defaultdict(int)
        dic[0] = 1
        for i in range(len(nums)):
            cur_sum += nums[i] % 2
            if cur_sum - k in dic:
                res += dic[cur_sum-k]
            dic[cur_sum] += 1
        return res

time complexity: $O(n)$
space complexity: $O(1)$
reference:
related problem: