Leetcode problem 110 - 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 is 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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numberOfSubarrays = function (nums, k) {
  // Initialize index to keep track of the start of the current subarray
  let index = 0;

  // Initialize prefix to store the length of the current subarray
  let prefix = 0;

  // Initialize countOdd to track the number of odd elements encountered in the subarray
  let countOdd = 0;

  // Initialize count to keep track of the total count of valid subarrays
  let count = 0;

  // Iterate through the elements in the nums array
  for (let i = 0; i < nums.length; i++) {
    // Check if the current element is odd
    if (nums[i] % 2 === 1) {
      // Reset prefix and increment countOdd when an odd element is encountered
      prefix = 0;
      countOdd++;
    }

    // Check if the count of odd elements in the subarray is equal to k
    while (countOdd === k && index <= i) {
      // Check if the element at the start of the subarray is odd
      if (nums[index] % 2 === 1) {
        // Decrease the count of odd elements in the subarray
        countOdd--;
      }

      // Move the start index to the right and increment the prefix length
      index++;
      prefix++;
    }

    // Add the length of the current subarray to the total count
    count += prefix;
  }

  // Return the total count of valid subarrays
  return count;
};

The time complexity of this code is O(n), where n is the length of the input array nums. This is because the code uses a single for loop that iterates through each element of the array once.

The space complexity of this code is O(1), as it only uses a constant amount of additional space to store the variables index, prefix, countOdd, and count. The space used does not depend on the size of the input array.