Count Number Of Nice Subarrays - Leetcode Solution

Problem:

Given an array of integers nums and an integer k. A 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,1] and [1,2,1,1].

Example 2:

Input: nums = [2,4,6], k = 1

Output: 0

Explanation: There is no odd numbers in the array.

Approach:

To solve this problem, we have to use the sliding window technique. We will maintain two pointers left and right and count the number of odd numbers between them. Whenever the count is less than k, we will increment the right pointer. If the count becomes greater than k, we will increment the left pointer to reduce the count of odd numbers.

We will maintain a variable called result to count the number of nice sub-arrays. Whenever we get a nice sub-array, we will add it to the result. At the end, we will return the result.

Algorithm:

1. Initialize two pointers left and right to 0 and count to 0
2. Initialize result to 0
3. Iterate through the array while right < n: a. If the number at nums[right] is odd, increment count b. While count is greater than k: i. If the number at nums[left] is odd, decrement count ii. Increment left pointer c. If count is equal to k, increment result by 1 d. Increment right pointer
4. Return the result

Code:

public int numberOfSubarrays(int[] nums, int k) { int left = 0, right = 0, count = 0, result = 0; int n = nums.length; while (right < n) { if (nums[right] % 2 == 1) { count++; } while (count > k) { if (nums[left] % 2 == 1) { count--; } left++; } if (count == k) { result++; } right++; } return result; }

Complexity Analysis:

1. Time Complexity: O(n)
2. Space Complexity: O(1)

The time complexity of the algorithm is O(n) because we are traversing the array once. The space complexity of the algorithm is O(1) because we are not using any extra space.

1