1248. Count Number of Nice Subarrays

1248. Count Number of Nice Subarrays

Question

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

Algorithm

1. The nice sub array is the subarray with k odd number

2. I was thinking of using sliding window , why? Because we are manipulating subarrays and sliding window can help in most case. (Note: non negative elements array)

3. But I was stuck at the shrink -> what should I do to record the current accumulated result or find res. For example [2,2,2,1,2,2,1,2,2,2] when the left is 1 and right is 1, how we get the current qualified subarray count from this ?

4. We can't with existing values -> additional information needed -> lastPopped

   Step 4 is the mind gap with the answer.

5. With lastPopped, we can get the sub result (subarrays count starting from left, ending at right) -> initialGap

6. The gap is calculated by left - last popped -> this is the number / count current subarray can propose . For example [2,2,2,1,2,2,1,2,2,2] when the left is 1 and right is 1, the gap is 4 -> why

7. It's [2,2,2,1,2,2,1], [2,2,1,2,2,1], [2,1,2,2,1], [1,2,2,1], so the gap is the count

Implementation

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Queue<Integer> queue = new LinkedList<>();
        int res = 0;
        int lastPopped = -1;
        int initialGap = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                queue.offer(i);
            }
            if (queue.size() > k) {
                lastPopped = queue.poll();
            }

            if (queue.size() == k) {
                initialGap = queue.peek() - lastPopped;
                res += initialGap;
            }
        }
        return res;
    }
}