Count Number of Nice Subarrays - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given an integer array and an integer k. A subarray is considered nice if it contains exactly k odd numbers. The goal is to count how many such subarrays exist. Since subarrays are contiguous, the solution relies on efficiently tracking odd-number counts while scanning the array.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
The straightforward method checks every possible subarray. Start from each index i, extend the subarray to the right, and keep a running count of odd numbers. Every time the odd count equals k, increment the answer. If the count exceeds k, you can stop extending that subarray because additional elements will only increase the count further. This approach uses simple iteration and parity checks (num % 2) without extra data structures. While easy to implement, the nested iteration leads to O(n²) time complexity, which becomes slow for large arrays.
Approach 2: Two-Pointer / Sliding Window (O(n) time, O(1) space)
The optimal approach uses the sliding window technique to count subarrays with at most k odd numbers. If you can compute the number of subarrays with at most k odds and subtract the number with at most k-1 odds, the result equals the number with exactly k odds. Maintain two pointers (left and right) while scanning the array. Expand the window by moving right, update the odd count, and shrink from the left whenever the count exceeds k. For each valid window, add right - left + 1 to the result because all subarrays ending at right and starting within the window are valid.
This works because the window always maintains the constraint of at most k odd numbers. Each element enters and leaves the window at most once, giving a linear scan. The approach effectively converts a counting problem into a window expansion problem, which is a common pattern in sliding window and prefix sum-style problems.
Recommended for interviews: Interviewers typically expect the O(n) sliding window solution. It shows you understand how to transform “exactly k” constraints into two “at most k” computations and manage dynamic windows efficiently. The brute force approach demonstrates baseline reasoning about subarrays, but the two-pointer optimization shows stronger algorithmic insight and familiarity with common hash table and window-counting patterns used in array problems.
Approach 1: Two-Pointer or Sliding Window Approach
The main idea is to use a sliding window to keep track of the current subarray and count of odd numbers. If the count of odd numbers becomes more than k, move the start pointer to decrease the count. For every suitable subarray, calculate the number of possible subarrays that end at the current end pointer. This way, we can efficiently count the nice subarrays.
This solution uses a hash map (dictionary) to count the frequency of certain odd counts (prefix counts). As we iterate over nums, we update the current count of odd numbers. If the current count minus k has been seen before, it means there is a subarray ending at the current position with exactly k odd numbers.
Code
Python
Java
C++
C#
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n) for the dictionary to store prefix counts.
Approach 2: Brute Force Approach
This approach involves checking every possible subarray of nums and counting the odd numbers in each. If a subarray contains exactly k odd numbers, it is counted as nice. While straightforward to implement, this method is not efficient for large arrays as its time complexity is quadratic.
This Python solution iterates over all possible subarrays starting from each index. For each subarray, it counts the number of odd numbers and checks if this matches k. If matched, the count of nice subarrays is incremented.
Code
Python
Java
C++
C#
JavaScript
Complexity
Time Complexity: O(n^2), where n is the length of nums.
Space Complexity: O(1)
Approach 3: Prefix Sum + Array or Hash Table
The problem asks for the number of subarrays that contain exactly k odd numbers. We can calculate the number of odd numbers t in each prefix array and record it in an array or hash table cnt. For each prefix array, we only need to find the number of prefix arrays with t-k odd numbers, which is the number of subarrays ending with the current prefix array.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer or Sliding Window Approach | Time Complexity: O(n), where n is the length of the array. |
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of nums. |
| Prefix Sum + Array or Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem or when input size is very small. |
| Two-Pointer / Sliding Window | O(n) | O(1) | Best general solution for large arrays; interview-preferred due to linear scan. |
Video Solution
L10. Count number of Nice subarrays | 2 Pointers and Sliding Window Playlist • take U forward • 204,367 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Number of Nice Subarrays easy or hard?
Count Number of Nice Subarrays Python/Java solution
How to solve Count Number of Nice Subarrays in O(n)?
What is the best approach for Count Number of Nice Subarrays?
Is Count Number of Nice Subarrays asked at Google/Amazon/Meta?
What data structure is used in Count Number of Nice Subarrays?
What is the time complexity of Count Number of Nice Subarrays?
Ready to solve this problem?
Practice Count Number of Nice Subarrays with our built-in code editor and test cases.
Practice on FleetCode