DSA problem
Count Number of Nice Subarrays
Given an array of integers nums and an integer k, a subarray is called nice if it contains exactly k odd numbers. Return the number of nice subarrays. A subarray is a contiguous, non-empty sequence of elements within the array.
Counting subarrays with an exact property is harder than finding the longest or shortest one, because a plain expand-and-shrink window measures lengths rather than counts. The standard technique converts the exact constraint into the difference of two at-most constraints.
The key identity is that the number of subarrays with exactly k odd numbers equals the number with at most k odd numbers minus the number with at most k - 1 odd numbers. Each of those at-most quantities is easy to compute with a single sliding window, because the count of odd numbers in a window grows monotonically as the window extends.
The intuition for the sliding window is the helper function for at most m odds. Expand the right pointer and track how many odd numbers the window holds; whenever that count exceeds m, shrink from the left. After each expansion, every subarray ending at the right pointer and starting anywhere inside the current window is valid, so we add the window width to a running total. Subtracting the two helper results gives the exact answer in linear time.
Examples
nums = [1,1,2,1,1], k = 32nums = [2,4,6], k = 10nums = [2,2,2,1,2,2,1,2,2,2], k = 216Constraints
- 1 <= nums.length <= 50000
- 1 <= nums[i] <= 10^5
- 1 <= k <= nums.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.