DSA

Count Number of Nice Subarrays

PrefixSum + Hashmap approach. Optimal — Time O(n), Space O(n).

August 8, 2026

DSA Sliding Window Two Pointers LeetCode Practice

Practice Link

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.

Approach 1#

If we consider even number as 0 and odd as 1
This problem can be considered same as binary array with sum as k

Replace each number with its parity (0 for even, 1 for odd), which transforms the problem into counting subarrays of a binary array whose sum equals k. The same sliding-window trick from "Binary Subarrays With Sum" then applies: count(sum == k) = count(sum \<= k) − count(sum \<= k-1). This runs in O(n) time with O(1) extra space and avoids a hash map entirely.

Best for binary (0/1) arrays

cpp

class Solution {
public:

    int helper(vector<int> &nums, int k)
    {
        if(k<0)
            return 0;

        int l =0,r=0;

        int currSum=0,cnt=0;
        while(r<nums.size())
        {
            currSum += nums[r];
            while(currSum > k && l<=r)
            {
                currSum -= nums[l];
                l++;
            }
            cnt += (r-l+1);
            r++;
        }
        return cnt;
    }

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

    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;

        return findSubarraysWithSumInBinaryArray(nums, k); 
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Approach 2 - PrefixSum + Hashmap#

Count how many times a prefix sum of sum - k has appeared before by using a hash map. Each number is reduced to its parity inline (nums[i] % 2), and a running parity sum is tracked. Whenever prefixCount[sum - k] is non-zero, it means there are that many subarrays ending at the current index that contain exactly k odd numbers. This avoids the two-pass sliding-window trick but uses O(n) space for the hash map.

cpp

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        unordered_map<int,int> prefixCount;
        prefixCount[0]=1;
        int sum=0,cnt=0;

        for(int i=0;i<nums.size();i++)
        {
            nums[i] = nums[i]%2;
            sum += nums[i];
            if(prefixCount.count(sum-k))
                cnt += prefixCount[sum-k];
            prefixCount[sum]++;
        }
        return cnt;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

DSALongest Substring Without Repeating Characters5 approaches incl. Brute Force, Better, Optimized Approach: SLiding…, and more. Optimal — Time O(n), Space O(1).DSALongest Repeating Character ReplacementCovers: Btute Force, Optimal - Sliding Window. Optimal — Time O(n), Space O(1).DSABinary Subarrays With SumCovers: Prefixsum + Hashmap, Sliding window. Optimal — Time O(n), Space O(1).

Approach 1#

Approach 2 - PrefixSum + Hashmap#

Related articles