1248 Count Number of Nice Subarrays

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.

Example 1:

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:

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

Example 3:

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

Overview

Note that we are trying to find a contiguous subarray. In particular the subarray [1,1,1] from the first example is not sufficient.

Sliding Window Technique

Let’s work with the following example:

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

Suppose we know the index of an odd number in the array (index b), and we know the index of the k’th odd number following the odd number at index b. (index c)

[1,2,3,3,6,7]

       ↑ ↑                

       b c                

We see that the nice subarrays that contain exactly 2 odd numbers and encompass numbers at index b and c are as follows:

[2,3,3]

[3,3]

[3,3,6]

[2,3,3,6]

Take the index of the odd number preceding index b (index a) and take the index of the odd number proceeding index c (index d)

[1,2,3,3,6,7]

 ↑     ↑ ↑    ↑

 a     b c    d

Then we can compute the number of subarrays that contain exactly 2 odd numbers and encompass numbers at index b and c with the following formula:

We can then slide the indicies to the right and repeat this process.

[1,2,3,3,6,7]

       ↑ ↑     ↑ ↑

       a b     c d

In this case index d is out of bounds and will therefore take on the value of the length of the array.

class Solution:
    def numberOfSubarrays(self, nums, k) -> int:
        store = [-1]
        # Capture the index of each odd number in the list
        for i in range(len(nums)):
            if nums[i] % 2:
                store.append(i)

        store = store + [len(nums)]

        current = 1
        result = 0
        while current + k < len(store):
            result += (store[current] - store[current - 1]) * (store[current + k] - store[current + k - 1])
            current += 1

        return result