# Count Number of Nice Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-nice-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-nice-subarrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Deliveroo](https://scaleengineer.com/companies/deliveroo)
---
## Problem
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`

# Approaches
## Brute Force Enumeration
This is the most straightforward and intuitive approach. The idea is to generate every possible continuous subarray of the given array `nums`. For each subarray, we count the number of odd integers it contains. If this count is exactly equal to `k`, we increment a counter for nice subarrays. We repeat this process for all subarrays and return the final count.
**Time:** O(N^2), where N is the length of the array. The two nested loops lead to a quadratic time complexity, as we potentially check every subarray. · **Space:** O(1), as we only use a constant number of variables to store counts and indices.
**Pros:** Simple to understand and easy to implement.; Requires no extra space besides a few counter variables.
**Cons:** Highly inefficient for large inputs.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms given the problem constraints (N up to 50000).
### Explanation
We can implement this using two nested loops. The outer loop selects the starting index `i` of the subarray, and the inner loop selects the ending index `j`. For each pair of `(i, j)`, we have a subarray `nums[i...j]`. A running count of odd numbers is maintained for the subarray as the inner loop progresses. When the count of odd numbers reaches `k`, we've found a nice subarray and increment our result. A small optimization can be made: if the count of odd numbers exceeds `k`, we can stop extending the current subarray (break the inner loop) since it can no longer become a nice subarray with exactly `k` odd numbers.

```java
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int oddCount = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] % 2 != 0) {
                    oddCount++;
                }
                if (oddCount == k) {
                    count++;
                } else if (oddCount > k) {
                    // Optimization: No need to check further for this starting 'i'
                    break;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a variable `nice_count` to 0.
- Use a nested loop structure. The outer loop with index `i` iterates from `0` to `n-1` to fix the starting point of a subarray.
- The inner loop with index `j` iterates from `i` to `n-1` to fix the ending point of the subarray.
- For each subarray `nums[i...j]`, maintain a count of odd numbers within it, let's call it `odd_count`.
- As the inner loop extends the subarray by one element `nums[j]`, update `odd_count`.
- If `odd_count` becomes equal to `k`, it means the current subarray `nums[i...j]` is nice, so we increment `nice_count`.
- If `odd_count` exceeds `k`, we can break the inner loop because any further extension of the subarray from this starting point `i` will also have more than `k` odd numbers.
- After iterating through all possible start and end points, return the final `nice_count`.

## Prefix Sum with Hashing
A more efficient approach uses the concept of prefix sums (or in this case, prefix counts of odd numbers). The number of odd numbers in any subarray `nums[i..j]` can be calculated as `(total odd numbers up to index j) - (total odd numbers up to index i-1)`. We want this difference to be `k`.

By rearranging the equation `prefix_odd_count[j] - prefix_odd_count[i-1] = k`, we get `prefix_odd_count[i-1] = prefix_odd_count[j] - k`. This means that for each index `j`, we need to find how many previous indices `i-1` satisfy this condition. A hash map is perfect for this, allowing us to store and retrieve the frequencies of prefix odd counts in O(1) time on average.
**Time:** O(N), as we iterate through the array only once. Hash map get and put operations take O(1) time on average. · **Space:** O(N) in the worst case. If the number of odd numbers increases with each element, the hash map could store up to N+1 distinct prefix counts.
**Pros:** Efficient single-pass O(N) time complexity.; Conceptually applicable to a wide range of subarray sum/count problems.
**Cons:** Requires extra space for the hash map, which can be up to O(N) in the worst-case scenario.
### Explanation
We iterate through the array once, maintaining a running count of odd numbers encountered so far (`currentOddCount`). We use a hash map to store the frequencies of these running counts. For each element, we calculate the `target` prefix count we need (`currentOddCount - k`). We then query the hash map for the frequency of this `target` count and add it to our total result. Finally, we update the hash map with the `currentOddCount`. We must initialize the map with a count of 1 for a prefix odd count of 0 to correctly handle subarrays that start from the beginning of the array.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1); // Base case for subarrays starting at index 0
        
        int count = 0;
        int currentOddCount = 0;
        
        for (int num : nums) {
            if (num % 2 != 0) {
                currentOddCount++;
            }
            
            // We need a prefix sum 'p' such that currentOddCount - p = k
            // which means p = currentOddCount - k
            int target = currentOddCount - k;
            count += prefixCounts.getOrDefault(target, 0);
            
            // Update the map with the frequency of the current prefix odd count
            prefixCounts.put(currentOddCount, prefixCounts.getOrDefault(currentOddCount, 0) + 1);
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0` and `odd_count = 0`.
- Create a hash map `prefix_counts` to store the frequency of each prefix odd count. Initialize it with `prefix_counts.put(0, 1)` to account for subarrays starting at index 0.
- Iterate through each number `num` in the input array `nums`.
- If `num` is odd, increment the running `odd_count`.
- At each element, we have the current prefix odd count (`odd_count`). We need to find a previous prefix odd count `p` such that `odd_count - p = k`. This is equivalent to `p = odd_count - k`.
- Check if the map `prefix_counts` contains the key `odd_count - k`. If it does, it means there are `prefix_counts.get(odd_count - k)` subarrays that can end just before our current position to form a valid nice subarray. Add this frequency to the total `count`.
- Update the map with the current `odd_count` by incrementing its frequency: `prefix_counts.put(odd_count, prefix_counts.getOrDefault(odd_count, 0) + 1)`.
- After the loop finishes, return `count`.

## Sliding Window using "At Most K"
This is a very efficient and space-optimal approach that uses a clever trick. Directly counting subarrays with *exactly* `k` odd numbers with a single sliding window can be complex. Instead, we can solve a simpler problem: counting subarrays with *at most* `k` odd numbers. The number of subarrays with exactly `k` odd numbers is then the difference between the number of subarrays with at most `k` odd numbers and the number of subarrays with at most `k-1` odd numbers.
**Time:** O(N). The `atMost` helper function uses a sliding window where each pointer, `left` and `right`, traverses the array at most once. Since we call it twice, the total time complexity is O(N) + O(N) = O(N). · **Space:** O(1). This approach is highly space-efficient as it only uses a few variables for pointers and counts, regardless of the input size.
**Pros:** Optimal O(N) time complexity.; Optimal O(1) space complexity, making it the most memory-efficient solution.; It's a powerful pattern applicable to many similar 'exactly k' type problems.
**Cons:** The logic of converting an 'exactly k' problem into two 'at most k' problems might not be immediately obvious.
### Explanation
We create a helper function that implements a sliding window to count subarrays with at most a certain number of odd elements. This helper, `atMost(limit)`, maintains a window `[left, right]` and expands it by moving `right`. If the number of odd elements in the window exceeds the `limit`, it shrinks the window by moving `left` forward until the condition is met again. For every valid window ending at `right`, there are `right - left + 1` valid subarrays. By calling this helper function for `k` and `k-1` and taking the difference, we isolate the count for subarrays with exactly `k` odd numbers.

```java
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        // The number of subarrays with exactly k odd numbers is
        // (number of subarrays with at most k odd numbers) - 
        // (number of subarrays with at most k-1 odd numbers).
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    /**
     * Helper function to count the number of subarrays with at most k odd numbers.
     */
    private int atMost(int[] nums, int k) {
        int count = 0;
        int left = 0;
        int oddCount = 0;
        
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 != 0) {
                oddCount++;
            }
            
            // If the window has more than k odd numbers, shrink it from the left.
            while (oddCount > k) {
                if (nums[left] % 2 != 0) {
                    oddCount--;
                }
                left++;
            }
            
            // For a valid window [left, right], all subarrays ending at 'right'
            // are also valid. The number of such subarrays is (right - left + 1).
            count += (right - left + 1);
        }
        
        return count;
    }
}
```
### Algorithm
- The core idea is that `count(exactly k) = count(at most k) - count(at most k-1)`.
- Implement a helper function, `atMost(k)`, that counts subarrays with at most `k` odd numbers using a sliding window.
- **Inside `atMost(k)`:**
  - Initialize `left = 0`, `result = 0`, and `odd_count = 0`.
  - Iterate through the array with a `right` pointer from `0` to `n-1`.
  - If `nums[right]` is odd, increment `odd_count`.
  - While `odd_count > k`, the window is invalid. Shrink the window from the left by incrementing `left`. If `nums[left]` was odd, decrement `odd_count`.
  - Once the window `[left...right]` is valid (has at most `k` odd numbers), all subarrays ending at `right` that start at or after `left` are also valid. The number of such subarrays is `right - left + 1`. Add this to `result`.
  - Return `result`.
- The final answer is `atMost(k) - atMost(k-1)`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfSubarrays(int[] nums, int k) {
    int n = nums.length;
    int[] cnt = new int[n + 1];
    cnt[0] = 1;
    int ans = 0, t = 0;
    for (int v : nums) {
      t += v & 1;
      if (t - k >= 0) {
        ans += cnt[t - k];
      }
      cnt[t]++;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfSubarrays(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> cnt(n + 1);
    cnt[0] = 1;
    int ans = 0, t = 0;
    for (int &v : nums) {
      t += v & 1;
      if (t - k >= 0) {
        ans += cnt[t - k];
      }
      cnt[t]++;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int: cnt = Counter({0: 1}) ans = t = 0 for v in nums: t += v & 1 ans += cnt[t - k] cnt[t] += 1 return ans

```