Count Number of Nice Subarrays

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:

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 are no odd numbers in the array.

Example 3:

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

Formulate a solution in Python for this algorithmic problem.

Problem: Number of Nice Subarrays

Given an array of integers nums and an integer k, a continuous subarray is called nice if there are k odd numbers in it. The task is to return the number of nice sub-arrays.

Brute Force Solution

A naive approach is to iterate through all possible subarrays, count the number of odd numbers in each subarray, and increment a counter if the subarray is nice. This approach has a time complexity of O(n^2).

def numberOfSubarrays_brute_force(nums, k):
    count = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            odd_count = 0
            for num in subarray:
                if num % 2 != 0:
                    odd_count += 1
            if odd_count == k:
                count += 1
    return count

Optimal Solution: Sliding Window

A more efficient approach is to use a sliding window technique. We can maintain a window and expand it until it contains k odd numbers. Then, we can shrink the window from the left until it has less than k odd numbers. During this process, we count the number of valid subarrays.

def numberOfSubarrays(nums, k):
    n = len(nums)
    odd_indices = [-1]
    for i in range(n):
        if nums[i] % 2 != 0:
            odd_indices.append(i)
    odd_indices.append(n)
    
    if len(odd_indices) - 2 < k:
        return 0
    
    count = 0
    for i in range(1, len(odd_indices) - k):
        left = odd_indices[i] - odd_indices[i-1]
        right = odd_indices[i+k] - odd_indices[i+k-1]
        count += left * right
        
    return count

Example Walkthrough

Let's consider nums = [2,2,2,1,2,2,1,2,2,2] and k = 2.

1. Find the indices of the odd numbers: odd_indices = [-1, 3, 6, 10].
2. Iterate through the odd_indices to form windows of size k+1 (3 in this case).
3. For the first window [-1, 3, 6]: left = 3 - (-1) = 4, right = 10 - 6 = 4. The number of subarrays is 4 * 4 = 16.

Example Code

nums = [2,2,2,1,2,2,1,2,2,2]
k = 2
print(numberOfSubarrays(nums, k)) # Output: 16

Big(O) Run-time Analysis

The optimal solution iterates through the nums array once to find odd number indices, which takes O(n) time. Then, it iterates through odd_indices once, which takes at most O(n) time in the worst case. The calculations inside the loop take constant time O(1). Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis

The odd_indices array stores the indices of odd numbers. In the worst case, all numbers in nums are odd, and odd_indices will have a size of n+2. Therefore, the space complexity is O(n).

Edge Cases

• Empty array: If the input array nums is empty, the function should return 0.
• k is zero: If k is zero, the function should return the number of subarrays with zero odd numbers. This would require a slight modification to the sliding window.
• k is greater than the number of odd numbers in nums: If k is greater than the number of odd numbers in nums, then no nice sub-arrays exist and the function should return 0.
• No odd numbers in nums: If there are no odd numbers in nums and k > 0, the function should return 0.