Count Number of Nice Subarrays | Leetcode 1248

The problem “Count Number of Nice Subarrays” asks: given an integer array nums and an integer k, count the number of contiguous subarrays that contain exactly k odd numbers. This is a perfect use case for the at-most trick: count subarrays with at most k odds, subtract subarrays with at most k−1 odds. The difference gives exactly k odds.

Here’s the [Problem Link] to begin with.

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

Optimal Solution: Sliding Window (At-Most → Exact)

Intuition and Approach

• Maintain a window [left..right] and track Sum = number of odds in the window.
• Expand right; add nums[right] % 2 to Sum.
• While Sum > goal, shrink from the left, subtracting nums[left] % 2, and increment left.
• For each right, after enforcing Sum ≤ goal, all subarrays ending at right and starting from any index in [left..right] are valid, contributing (right − left + 1) to the count.
• Do this once for goal = k and once for goal = k−1; the difference is the number of subarrays with exactly k odds.

Code

class Solution:
    def countSubArrayLessThanOrEqualToGoal(self, nums, goal):
        if goal < 0:
            return 0
        count = 0
        n = len(nums)
        left = 0
        right = 0
        Sum = 0
        while right < n:
            # Add 1 if nums[right] is odd, else add 0
            Sum += nums[right] % 2
            # Shrink window until number of odds <= goal
            while Sum > goal:
                Sum -= nums[left] % 2
                left += 1
            # All subarrays ending at right and starting from [left..right] are valid
            count = count + ((right - left) + 1)
            right += 1
        return count

    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return self.countSubArrayLessThanOrEqualToGoal(
            nums, k
        ) - self.countSubArrayLessThanOrEqualToGoal(nums, k - 1)

Why This Works

• The window always satisfies “number of odds ≤ goal.”
• For each right, once the window is valid, every start position from left to right yields a valid subarray, hence (right − left + 1) contributions.
• exact K = atMost(K) − atMost(K−1) is a standard identity that converts exact counting into two linear at-most counts.

Complexity

• Time: O(n) – each index is visited at most twice (once by right, once by left).
• Space: O(1) – constant auxiliary variables.

Tips and Edge Cases

• If k = 0, answer counts subarrays with zero odd numbers (i.e., all-even subarrays); the formula still works because atMost(−1) returns 0 by guard.
• The method is robust for any non-negative k and any integers in nums—only odd/even matters.
• If you prefer prefix-sum + hashmap, you can map odds to 1, evens to 0, and count subarrays with sum k in O(n) time but O(n) space. The sliding-window at-most trick achieves O(1) space.

Takeaway

Transforming the array into oddness (0/1) and using the identity exact K = atMost(K) − atMost(K−1) lets you solve “Count Number of Nice Subarrays” in a clean, linear-time, constant-space manner—ideal for interviews and production.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.