{x}
blog image

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

 

Constraints:

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

Solution Explanation for Count Number of Nice Subarrays

This problem asks to find the number of subarrays within a given array nums that contain exactly k odd numbers. The most efficient approach leverages the concept of prefix sums and a hash map (or array in this case).

Approach:

  1. Prefix Sum of Odd Numbers: We iterate through the nums array. For each element, we check if it's odd (using the bitwise AND operator & 1). If it's odd, we increment a counter t. t essentially represents the prefix sum of odd numbers encountered so far.

  2. Hash Map (or Array): We use a hash map (or an array in this implementation which performs better due to its consistent time complexity) cnt to store the frequency of each prefix sum of odd numbers encountered. cnt[i] will store the number of times we've seen a prefix sum of i odd numbers. We initialize cnt[0] = 1 because an empty subarray has a prefix sum of 0 odd numbers.

  3. Counting Nice Subarrays: For each element, after updating t, we check if t - k is a valid key (index) in our hash map (i.e., t-k >=0). If it is, it means we've previously encountered a prefix sum with t - k odd numbers. The number of times we've seen this prefix sum (cnt[t - k]) represents the number of subarrays that, when appended with the current subarray ending at this point, would result in a nice subarray (exactly k odd numbers). We add cnt[t - k] to our answer ans.

  4. Updating Frequency: Finally, we increment the frequency count of the current prefix sum t in our hash map: cnt[t]++.

Time Complexity: O(n), where n is the length of nums. We iterate through the array once. Hash map lookups and insertions are considered O(1) on average. Using an array directly would also have O(1) complexity.

Space Complexity: O(n) in the worst case, as the hash map (or array) could potentially store counts for all prefix sums up to n.

Code Examples:

The provided code snippets in Python, Java, C++, Go, and TypeScript all implement this approach. They differ slightly in syntax, but the core logic remains the same. The use of an array instead of a hash map (except in the Python example which uses Counter which is efficient) in the Java, C++, Go, and TypeScript versions is a key optimization for consistent time complexity.

Example Walkthrough (Python):

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

| Iteration | v | t | t - k | cnt | ans | | --------- | --- | --- | ------- | --------------------------- | ----- | | 1 | 1 | 1 | -2 | {0: 1} | 0 | | 2 | 1 | 2 | -1 | {0: 1, 1: 1, 2:1} | 0 | | 3 | 2 | 2 | -1 | {0: 1, 1: 1, 2:1} | 0 | | 4 | 1 | 3 | 0 | {0: 1, 1: 1, 2:1, 3:1} | 1 | | 5 | 1 | 4 | 1 | {0: 1, 1: 2, 2:1, 3:1, 4:1} | 3 |

The final answer ans is 2 (as explained in the problem statement). Note that the Python Counter object automatically handles missing keys. The other examples use explicit checks to prevent index out of bounds errors.