Count Number of Nice Subarrays

Sliding WindowPrefix Sum

25 min

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" subarrays.

Example

Example 1:

Input: nums = [1,1,2,1,1], k = 3

nums: [1, 1, 2, 1, 1], k: 3

Output: 2

The nice subarrays are [1,1,2,1] and [1,2,1,1].

Solution

A clever way to solve this problem is to use the "at most" technique. The number of subarrays with exactly `k` odd numbers is equal to the number of subarrays with at most `k` odd numbers minus the number of subarrays with at most `k-1` odd numbers.

Algorithm Steps

Create a helper function `atMost(k)` that counts the number of subarrays with at most `k` odd numbers.
Inside `atMost(k)`, use a sliding window. Initialize `count` to 0, `l` to 0, and `res` to 0.
Iterate with a right pointer `r`. If `nums[r]` is odd, decrement `k`.
While `k` is less than 0, if `nums[l]` is odd, increment `k`. Then, increment `l`.
Add the size of the current valid window (`r - l + 1`) to `res`.
The final result is `atMost(k) - atMost(k - 1)`.

Count Number of Nice Subarrays

"At Most" Sliding Window Approach

Progress (atMost(k))1 / 1

Ready to start the visualization

nums

Odd Count

Subarrays (atMost(k))

Count Number of Nice Subarrays Solution


class Solution:
    def numberOfSubarrays(self, nums: list[int], k: int) -> int:
        def atMost(k):
            res = l = 0
            for r in range(len(nums)):
                k -= nums[r] % 2
                while k < 0:
                    k += nums[l] % 2
                    l += 1
                res += r - l + 1
            return res

        return atMost(k) - atMost(k - 1)