Code Implementation

class Solution:
    def numberOfSubarrays(self, nums, k):
        from collections import defaultdict
        count = defaultdict(int)
        count[0] = 1
        res = odd = 0
        for num in nums:
            odd += num % 2
            res += count[odd - k]
            count[odd] += 1
        return res
      

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        count[0] = 1;
        int odd = 0, res = 0;
        for (int num : nums) {
            odd += num % 2;
            res += count[odd - k];
            count[odd]++;
        }
        return res;
    }
};
      

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        int odd = 0, res = 0;
        for (int num : nums) {
            odd += num % 2;
            res += count.getOrDefault(odd - k, 0);
            count.put(odd, count.getOrDefault(odd, 0) + 1);
        }
        return res;
    }
}
      

var numberOfSubarrays = function(nums, k) {
    let count = {0: 1};
    let odd = 0, res = 0;
    for (let num of nums) {
        odd += num % 2;
        res += count[odd - k] || 0;
        count[odd] = (count[odd] || 0) + 1;
    }
    return res;
};
      

Problem Description

Given an array of integers nums and an integer k, you are asked to count the number of "nice" subarrays. A "nice" subarray is defined as a continuous subarray that contains exactly k odd numbers.

• Each subarray must be contiguous (i.e., elements are consecutive in the original array).
• You may not reuse elements between subarrays; each subarray is counted separately.
• There may be multiple valid subarrays, and you are to count all of them.
• Constraints typically ensure 1 <= nums.length <= 50000 and 1 <= nums[i] <= 10^5.

Your goal is to return the total number of such "nice" subarrays.

Thought Process

The most straightforward way to solve this problem is to consider every possible subarray and count the number of odd numbers in each. However, this brute-force approach is inefficient for large arrays because there are O(n²) possible subarrays.

To optimize, we notice that we are interested in subarrays with exactly k odd numbers. Instead of checking every subarray, we can keep track of the number of odd numbers seen so far as we iterate through the array. If we know how many times we've seen a certain count of odd numbers before, we can quickly determine how many subarrays ending at the current index have exactly k odd numbers.

This leads us to consider prefix sums and hash maps to count the occurrences of different "odd count" values efficiently, reducing the number of operations required.

Solution Approach

We solve the problem using a prefix sum and hash map approach:

1. Track the number of odd numbers (prefix sum): As we iterate through the array, we keep a running count of how many odd numbers we have seen up to the current index.
2. Use a hash map to record occurrences: For each value of the running odd count, we store how many times it has occurred so far in a hash map (dictionary). This allows us to efficiently look up how many times we have seen a prefix with exactly odd - k odd numbers.
3. Count valid subarrays: At each step, if we have previously seen a prefix with odd - k odd numbers, it means the subarray between that prefix and the current index contains exactly k odd numbers. We add the number of such prefixes to our result.
4. Initialization: We initialize the hash map with count[0] = 1 to handle the case where the subarray starts from the beginning.

This approach ensures that each element is processed only once, and all lookups and updates in the hash map are O(1).

Example Walkthrough

Let's walk through an example with nums = [1, 1, 2, 1, 1] and k = 3.

• Step 0: odd = 0, count = {0: 1}, res = 0
• Step 1: num = 1 (odd), odd = 1, count[1-3] = count[-2] = 0, res = 0, count[1] += 1 → count = {0:1, 1:1}
• Step 2: num = 1 (odd), odd = 2, count[2-3] = count[-1] = 0, res = 0, count[2] += 1 → count = {0:1, 1:1, 2:1}
• Step 3: num = 2 (even), odd = 2, count[2-3] = count[-1] = 0, res = 0, count[2] += 1 → count = {0:1, 1:1, 2:2}
• Step 4: num = 1 (odd), odd = 3, count[3-3] = count[0] = 1, res = 1, count[3] += 1 → count = {0:1, 1:1, 2:2, 3:1}
• Step 5: num = 1 (odd), odd = 4, count[4-3] = count[1] = 1, res = 2, count[4] += 1 → count = {0:1, 1:1, 2:2, 3:1, 4:1}

The final result is 2, corresponding to the subarrays [1,1,2,1] and [1,2,1,1] that each contain exactly 3 odd numbers.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) because for each starting index, we check every possible ending index and count odds.
  • Space Complexity: O(1) (no extra space beyond variables).
• Optimized prefix sum approach:
  • Time Complexity: O(n) since we traverse the array once and each hash map operation is O(1).
  • Space Complexity: O(n) in the worst case (if all prefix sums are unique).

Summary

The key insight for this problem is to transform the requirement of finding subarrays with exactly k odd numbers into a prefix sum problem, where we keep track of the cumulative count of odd numbers. By using a hash map to record the frequency of each odd count, we can instantly determine how many subarrays ending at the current index are "nice." This approach is efficient, elegant, and leverages common prefix sum and hash map strategies to solve what would otherwise be a computationally intensive problem.