1248. 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 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

Approach 01:

#include <vector>

class Solution {
public:
    int numberOfSubarrays(std::vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

private:
    int atMost(const std::vector<int>& nums, int k) {
        int count = 0;
        int left = 0;
        int odd_count = 0;

        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] % 2 == 1) {
                odd_count++;
            }
            while (odd_count > k) {
                if (nums[left] % 2 == 1) {
                    odd_count--;
                }
                left++;
            }
            count += right - left + 1;
        }

        return count;
    }
};

from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(k: int) -> int:
            count = 0
            i = 0
            odd_count = 0
            for j in range(len(nums)):
                if nums[j] % 2 == 1:
                    odd_count += 1
                while odd_count > k:
                    if nums[i] % 2 == 1:
                        odd_count -= 1
                    i += 1
                count += j - i + 1
            return count
        
        # Number of subarrays with exactly k odd numbers
        return atMost(k) - atMost(k - 1)

Time Complexity Analysis

• Function atMost:
  • The outer loop iterates over each element of the nums array exactly once.
  • The inner while loop ensures that each element is processed at most once by both the left and right pointers.

Therefore, the time complexity of the atMost function is O(n), where nnn is the length of the nums array.

• Overall Complexity:
  • The numberOfSubarrays function calls the atMost function twice, resulting in a total time complexity of O(n)+O(n)=O(n).

Space Complexity

The space complexity is O(1) since we use a fixed amount of extra space.