Count Number of Nice Subarrays
Understanding the Problem
We need to count how many contiguous subarrays contain exactly k odd numbers. Only parity matters: each element is either odd or even, and the even numbers never affect whether a subarray qualifies.
If we strip away the even numbers and think about where the odd numbers sit, the problem becomes choosing windows that capture exactly k of them. Even numbers at the edges of such a window add flexibility, because the boundaries can extend through them without changing the odd count. That flexibility is what makes the answer larger than the number of odd-number groups alone.
This is an "exactly k" counting problem. Two standard techniques apply: count prefix odd-totals with a hash map (the same idea as subarray-sum counting), or compute "at most k" minus "at most k-1" with a sliding window.
Key Constraints:
1 <= nums.length <= 50000- With n up to 50,000, we need O(n) or O(n log n). An O(n^2) brute force that checks every subarray would be 2.5 billion operations in the worst case, which is too slow.1 <= nums[i] <= 10^5- Values are positive integers. We only care about whether each value is odd or even, so the actual magnitude doesn't matter.1 <= k <= nums.length- k is at least 1, so we're always looking for subarrays with at least one odd number.
Approach 1: Brute Force
Intuition
Check every possible subarray and count how many odd numbers it contains. If the count equals k, the subarray is nice.
For each starting index, extend the subarray one element at a time while maintaining a running count of odd numbers. Once the count exceeds k, every longer subarray with the same start also exceeds k, so the inner loop can stop early.
Algorithm
- Initialize
result = 0to track the total count of nice subarrays. - For each starting index
ifrom0ton - 1: - Initialize
oddCount = 0. - For each ending index
jfromiton - 1: - If
nums[j]is odd, incrementoddCount. - If
oddCount == k, incrementresult. - If
oddCount > k, break the inner loop. - Return
result.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Two nested loops, each potentially scanning up to n elements. Early termination helps in practice but doesn't change the worst case.
- Space Complexity: O(1). Only a few integer variables regardless of input size.
The repeated work is the re-scan: each starting index counts odd numbers from scratch. Tracking the cumulative count of odd numbers once removes that re-scan and brings the time down to O(n).
Approach 2: Prefix Sum + Hash Map
Intuition
If we build a prefix sum where prefix[i] counts the number of odd numbers from the start of the array up to index i, then the number of odd numbers in any subarray nums[i..j] is prefix[j] - prefix[i-1]. So we need pairs where prefix[j] - prefix[i-1] = k, which means prefix[i-1] = prefix[j] - k.
As we iterate through the array, we maintain a hash map that stores how many times each prefix value has appeared. For each position j, we look up how many earlier positions had a prefix of prefix[j] - k. Each such position is the start of a distinct nice subarray ending at j, so we add that count to the result. Concretely, if 5 odd numbers have appeared by position j and k = 2, every earlier position with a prefix of 3 starts a nice subarray ending at j.
Algorithm
- Initialize
prefixCountmap with{0: 1}(the empty prefix has 0 odd numbers, and it occurs once). - Initialize
oddCount = 0andresult = 0. - For each element in
nums: - If the element is odd, increment
oddCount. - If
oddCount - kexists in the map, add its count toresult. - Increment
prefixCount[oddCount]by 1. - Return
result.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We iterate through the array once. Each iteration does O(1) work: a modulo check, a hash map lookup, and a hash map update.
- Space Complexity: O(n). The hash map stores at most n + 1 distinct prefix sum values.
The prefix sum approach runs in O(n) time but spends O(n) space on the hash map. A sliding window achieves the same time bound with constant space.
Approach 3: Sliding Window (At Most K Trick)
Intuition
Counting subarrays with exactly k odd numbers directly with a sliding window is awkward, because when the window holds exactly k, both expanding and shrinking can stay valid, so there is no single rule for moving the pointers. Counting subarrays with at most k odd numbers avoids this: expand the right end, and whenever the window has more than k odd numbers, shrink from the left. After the shrink, every subarray that ends at right and starts between left and right has at most k odd numbers, and there are right - left + 1 of them. Summing this at each step counts every valid subarray exactly once, at its right endpoint.
The identity exactly(k) = atMost(k) - atMost(k - 1) converts the easy count into the one we need. A subarray with at most k odd numbers has 0, 1, ..., or k of them; a subarray with at most k-1 has 0, 1, ..., or k-1. Subtracting cancels everything except the subarrays with exactly k odd numbers.
Algorithm
- Define a helper function
atMost(nums, k)that counts subarrays with at most k odd numbers: - Use two pointers
leftandrightstarting at 0. - Expand
rightthrough the array. Whennums[right]is odd, decrementk. - If
k < 0, shrink fromleftuntilk >= 0(incrementingkwhennums[left]is odd). - At each step, add
right - left + 1to the count. - Return
atMost(nums, k) - atMost(nums, k - 1).
Visualization and Code
Loading animation...
- Time Complexity: O(n). We call
atMosttwice, each doing a single pass through the array. Each pass is O(n) because the left pointer only moves forward. Total: O(2n) = O(n). - Space Complexity: O(1). Only a few integer variables. No hash map or additional data structure needed.