Count Number of Nice Subarrays
MedPrompt
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 sub-arrays.
Example 1:
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].Example 2:
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There are no odd numbers in the array.Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
Constraints:
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. The idea is to generate every possible continuous subarray of the given array nums. For each subarray, we count the number of odd integers it contains. If this count is exactly equal to k, we increment a counter for nice subarrays. We repeat this process for all subarrays and return the final count.
Algorithm
- Initialize a variable
nice_countto 0. - Use a nested loop structure. The outer loop with index
iiterates from0ton-1to fix the starting point of a subarray. - The inner loop with index
jiterates fromiton-1to fix the ending point of the subarray. - For each subarray
nums[i...j], maintain a count of odd numbers within it, let's call itodd_count. - As the inner loop extends the subarray by one element
nums[j], updateodd_count. - If
odd_countbecomes equal tok, it means the current subarraynums[i...j]is nice, so we incrementnice_count. - If
odd_countexceedsk, we can break the inner loop because any further extension of the subarray from this starting pointiwill also have more thankodd numbers. - After iterating through all possible start and end points, return the final
nice_count.
Walkthrough
We can implement this using two nested loops. The outer loop selects the starting index i of the subarray, and the inner loop selects the ending index j. For each pair of (i, j), we have a subarray nums[i...j]. A running count of odd numbers is maintained for the subarray as the inner loop progresses. When the count of odd numbers reaches k, we've found a nice subarray and increment our result. A small optimization can be made: if the count of odd numbers exceeds k, we can stop extending the current subarray (break the inner loop) since it can no longer become a nice subarray with exactly k odd numbers.
class Solution { public int numberOfSubarrays(int[] nums, int k) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { int oddCount = 0; for (int j = i; j < n; j++) { if (nums[j] % 2 != 0) { oddCount++; } if (oddCount == k) { count++; } else if (oddCount > k) { // Optimization: No need to check further for this starting 'i' break; } } } return count; }}Complexity
Time
O(N^2), where N is the length of the array. The two nested loops lead to a quadratic time complexity, as we potentially check every subarray.
Space
O(1), as we only use a constant number of variables to store counts and indices.
Trade-offs
Pros
Simple to understand and easy to implement.
Requires no extra space besides a few counter variables.
Cons
Highly inefficient for large inputs.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms given the problem constraints (N up to 50000).
A more efficient approach uses the concept of prefix sums (or in this case, prefix counts of odd numbers). The number of odd numbers in any subarray nums[i..j] can be calculated as (total odd numbers up to index j) - (total odd numbers up to index i-1). We want this difference to be k.
By rearranging the equation prefix_odd_count[j] - prefix_odd_count[i-1] = k, we get prefix_odd_count[i-1] = prefix_odd_count[j] - k. This means that for each index j, we need to find how many previous indices i-1 satisfy this condition. A hash map is perfect for this, allowing us to store and retrieve the frequencies of prefix odd counts in O(1) time on average.
Algorithm
- Initialize
count = 0andodd_count = 0. - Create a hash map
prefix_countsto store the frequency of each prefix odd count. Initialize it withprefix_counts.put(0, 1)to account for subarrays starting at index 0. - Iterate through each number
numin the input arraynums. - If
numis odd, increment the runningodd_count. - At each element, we have the current prefix odd count (
odd_count). We need to find a previous prefix odd countpsuch thatodd_count - p = k. This is equivalent top = odd_count - k. - Check if the map
prefix_countscontains the keyodd_count - k. If it does, it means there areprefix_counts.get(odd_count - k)subarrays that can end just before our current position to form a valid nice subarray. Add this frequency to the totalcount. - Update the map with the current
odd_countby incrementing its frequency:prefix_counts.put(odd_count, prefix_counts.getOrDefault(odd_count, 0) + 1). - After the loop finishes, return
count.
Walkthrough
We iterate through the array once, maintaining a running count of odd numbers encountered so far (currentOddCount). We use a hash map to store the frequencies of these running counts. For each element, we calculate the target prefix count we need (currentOddCount - k). We then query the hash map for the frequency of this target count and add it to our total result. Finally, we update the hash map with the currentOddCount. We must initialize the map with a count of 1 for a prefix odd count of 0 to correctly handle subarrays that start from the beginning of the array.
import java.util.HashMap;import java.util.Map; class Solution { public int numberOfSubarrays(int[] nums, int k) { Map<Integer, Integer> prefixCounts = new HashMap<>(); prefixCounts.put(0, 1); // Base case for subarrays starting at index 0 int count = 0; int currentOddCount = 0; for (int num : nums) { if (num % 2 != 0) { currentOddCount++; } // We need a prefix sum 'p' such that currentOddCount - p = k // which means p = currentOddCount - k int target = currentOddCount - k; count += prefixCounts.getOrDefault(target, 0); // Update the map with the frequency of the current prefix odd count prefixCounts.put(currentOddCount, prefixCounts.getOrDefault(currentOddCount, 0) + 1); } return count; }}Complexity
Time
O(N), as we iterate through the array only once. Hash map get and put operations take O(1) time on average.
Space
O(N) in the worst case. If the number of odd numbers increases with each element, the hash map could store up to N+1 distinct prefix counts.
Trade-offs
Pros
Efficient single-pass O(N) time complexity.
Conceptually applicable to a wide range of subarray sum/count problems.
Cons
Requires extra space for the hash map, which can be up to O(N) in the worst-case scenario.
This is a very efficient and space-optimal approach that uses a clever trick. Directly counting subarrays with exactly k odd numbers with a single sliding window can be complex. Instead, we can solve a simpler problem: counting subarrays with at most k odd numbers. The number of subarrays with exactly k odd numbers is then the difference between the number of subarrays with at most k odd numbers and the number of subarrays with at most k-1 odd numbers.
Algorithm
- The core idea is that
count(exactly k) = count(at most k) - count(at most k-1). - Implement a helper function,
atMost(k), that counts subarrays with at mostkodd numbers using a sliding window. - Inside
atMost(k):- Initialize
left = 0,result = 0, andodd_count = 0. - Iterate through the array with a
rightpointer from0ton-1. - If
nums[right]is odd, incrementodd_count. - While
odd_count > k, the window is invalid. Shrink the window from the left by incrementingleft. Ifnums[left]was odd, decrementodd_count. - Once the window
[left...right]is valid (has at mostkodd numbers), all subarrays ending atrightthat start at or afterleftare also valid. The number of such subarrays isright - left + 1. Add this toresult. - Return
result.
- Initialize
- The final answer is
atMost(k) - atMost(k-1).
Walkthrough
We create a helper function that implements a sliding window to count subarrays with at most a certain number of odd elements. This helper, atMost(limit), maintains a window [left, right] and expands it by moving right. If the number of odd elements in the window exceeds the limit, it shrinks the window by moving left forward until the condition is met again. For every valid window ending at right, there are right - left + 1 valid subarrays. By calling this helper function for k and k-1 and taking the difference, we isolate the count for subarrays with exactly k odd numbers.
class Solution { public int numberOfSubarrays(int[] nums, int k) { // The number of subarrays with exactly k odd numbers is // (number of subarrays with at most k odd numbers) - // (number of subarrays with at most k-1 odd numbers). return atMost(nums, k) - atMost(nums, k - 1); } /** * Helper function to count the number of subarrays with at most k odd numbers. */ private int atMost(int[] nums, int k) { int count = 0; int left = 0; int oddCount = 0; for (int right = 0; right < nums.length; right++) { if (nums[right] % 2 != 0) { oddCount++; } // If the window has more than k odd numbers, shrink it from the left. while (oddCount > k) { if (nums[left] % 2 != 0) { oddCount--; } left++; } // For a valid window [left, right], all subarrays ending at 'right' // are also valid. The number of such subarrays is (right - left + 1). count += (right - left + 1); } return count; }}Complexity
Time
O(N). The `atMost` helper function uses a sliding window where each pointer, `left` and `right`, traverses the array at most once. Since we call it twice, the total time complexity is O(N) + O(N) = O(N).
Space
O(1). This approach is highly space-efficient as it only uses a few variables for pointers and counts, regardless of the input size.
Trade-offs
Pros
Optimal O(N) time complexity.
Optimal O(1) space complexity, making it the most memory-efficient solution.
It's a powerful pattern applicable to many similar 'exactly k' type problems.
Cons
The logic of converting an 'exactly k' problem into two 'at most k' problems might not be immediately obvious.
Solutions
Solution
class Solution {public int numberOfSubarrays(int[] nums, int k) { int n = nums.length; int[] cnt = new int[n + 1]; cnt[0] = 1; int ans = 0, t = 0; for (int v : nums) { t += v & 1; if (t - k >= 0) { ans += cnt[t - k]; } cnt[t]++; } return ans; }}class Solution {public: int numberOfSubarrays(vector<int> &nums, int k) { int n = nums.size(); vector<int> cnt(n + 1); cnt[0] = 1; int ans = 0, t = 0; for (int &v : nums) { t += v & 1; if (t - k >= 0) { ans += cnt[t - k]; } cnt[t]++; } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.