LeetCode 1248: Count Number of Nice Subarrays

Explanation

To solve this problem, we can use a sliding window approach. We will maintain two pointers - left and right, and keep expanding the window until we have exactly k odd numbers in the window. For each valid window, we can calculate the number of subarrays that can be formed with that window as a nice subarray. We can keep track of the count of such subarrays and return the final result.

• Initialize left = 0, right = 0, count = 0, oddCount = 0, result = 0
• Iterate over the array while moving the right pointer:
  • If nums[right] is odd, increment oddCount
  • While oddCount == k, increment count for each valid window and move the left pointer:
    • While nums[left] is not odd, increment count and move left
    • After exiting the inner loop, calculate the number of subarrays that can be formed with the current window
    • Increment result by the count of subarrays
    • Move the left pointer to continue the search for more valid windows
• Return the final result

Time Complexity: O(N) where N is the number of elements in the array. Space Complexity: O(1)

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