Count Number of Nice Subarrays
Medium · Sliding Window · Array · Hash Table · Math · Sliding Window · Prefix Sum
Problem
Given an integer array nums and an integer k, a contiguous subarray is called nice if it contains exactly k odd numbers.
Return the number of nice subarrays.
Examples
Input: nums = [2,1,2,1,3], k = 2 Output: 4
The nice subarrays are [2,1,2,1], [1,2,1], [2,1,3] and [1,3].
Input: nums = [2,4], k = 1 Output: 0
The array contains no odd numbers.
Input: nums = [2,2,1,2,2], k = 1 Output: 9
The single 1 can be extended by 0, 1 or 2 evens on each side: 3 · 3 = 9.
Constraints
- 1 <= len(nums) <= 5 · 10^4
- 1 <= nums[i] <= 10^5
- 1 <= k <= len(nums)
Approaches
- Every start, extend until too many — time O(n²), space O(1)
Follow-up
Can you do it with two pointers and no table? Count subarrays with at most k odd numbers with a sliding window (every right end adds right - left + 1), then subtract the count for at most k - 1. “Exactly” is the difference of two “at most” counts.
Related problems
Start free on Cariara · Coding problems · System design studio
