1248. Count Number of Nice Subarrays

Problem Statement

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

Intuition

Approach1:
Convert odd and even to 1/0 
And apply prefix sum using hash map

Similar to above problem

Approach 2:

Slinding window 
Atmost k - Atmost k-1 approach

Links

https://leetcode.com/problems/count-number-of-nice-subarrays/description/

Video Links

https://www.youtube.com/watch?v=O0bbpT710KA&t=1s&ab_channel=CodingSamurai%27s

Approach 1:

MAp and Prefix sum

C++

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        for(int i=0; i<nums.size(); i++){
            if(nums[i]%2 == 0)
                nums[i] = 0;
            else
                nums[i] = 1;
        }

        unordered_map<int,int> mp;
        int pre=0, ans=0;
        mp[0]=1;

        for(int i=0; i<nums.size(); i++){
            pre += nums[i];

            if(mp.find(pre-k) != mp.end())
                ans += mp[pre-k];

            mp[pre]++;
        }

        return ans;
    }
};

Approach 2:

Sliding Window

C++

class Solution {
public:
    int Atmost(vector<int>& nums, int k){
        int ans=0, odd=0, low=0;

        for(int high=0; high<nums.size(); high++){
            if(nums[high]%2 != 0)
                odd++;

            while(odd>k){
                if(nums[low]%2 != 0)
                    odd--;

                low++;
            }
            /* Here at each step we are not getting array lenght 
                But actually num of arrays
                1 2 1 (1
                1, 11, 211, 1211 like that 4
                
            */
            ans += high-low+1;
        }

        return ans;
    }

    int numberOfSubarrays(vector<int>& nums, int k) {
        return Atmost(nums, k) - Atmost(nums, k-1);
    }
};

Approach 3:

C++

Approach 4:

C++