Count Number of Nice Subarrays — LeetCode 1248 Python Solution

The problem

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Example

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

Python solution

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt = Counter({0: 1})
        ans = t = 0
        for v in nums:
            t += v & 1
            ans += cnt[t - k]
            cnt[t] += 1
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1248. Count Number of Nice Subarrays is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems