Naive Approach (Brute Force)

The most straightforward approach is to consider all possible subarrays and count the number of odd numbers in each subarray. If a subarray contains exactly k odd numbers, we increment the count.

Algorithm

1. Iterate through all possible start indices of subarrays.
2. For each start index, iterate through all possible end indices.
3. For each subarray, count the number of odd numbers.
4. If the count equals k, increment the result.

Code (Python)

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

Time Complexity: O(n^3)

• Three nested loops are used: two for selecting subarrays and one for counting odd numbers within the subarray.

Space Complexity: O(1)

• Constant extra space is used.

Optimal Approach (Sliding Window)

A more efficient approach involves using a sliding window. The idea is to maintain a window and adjust its size such that it always contains k odd numbers. We can further optimize by counting the number of even numbers before the first odd number and after the last odd number in the window.

Algorithm

1. Use a helper function atMost(nums, k) which finds the number of subarrays with at most k odd numbers.
2. The result is atMost(nums, k) - atMost(nums, k - 1).

Helper Function atMost(nums, k)

1. Initialize left = 0, count = 0, and odd_count = 0.
2. Iterate through the array with right pointer.
3. If nums[right] is odd, increment odd_count.
4. While odd_count > k, move the left pointer and decrement odd_count if nums[left] is odd.
5. Add right - left + 1 to the count.
6. Return count.

Code (Python)

def numberOfSubarrays(nums, k):
    def atMost(nums, k):
        left = 0
        count = 0
        odd_count = 0
        for right in range(len(nums)):
            if nums[right] % 2 != 0:
                odd_count += 1
            while odd_count > k:
                if nums[left] % 2 != 0:
                    odd_count -= 1
                left += 1
            count += right - left + 1
        return count

    return atMost(nums, k) - atMost(nums, k - 1)

Time Complexity: O(n)

• We iterate through the array at most twice.

Space Complexity: O(1)

• Constant extra space is used.

Edge Cases

1. Empty Array: The code handles empty arrays correctly as the loops won't execute, returning 0.
2. k = 0: If k is 0, the atMost function will count subarrays with no odd numbers.
3. k > Number of Odd Numbers in Array: The atMost(nums, k-1) will return a non-zero value and ensures the correct result even when k exceeds the number of odd numbers in the array
4. All Even Numbers: If the array contains only even numbers and k > 0, the function returns 0, which is correct.