Count Number of Nice Subarrays — Problem & Solution
Count Number of Nice Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Number of Nice Subarrays is a medium coding problem on arrays, hash table and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of integers nums and an integer k, a subarray is nice if it contains exactly k odd numbers.
Return the number of nice subarrays.
Example 1
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The nice subarrays 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 at all.
Example 3
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
Constraints
1 <= nums.length <= 401 <= nums[i] <= 10001 <= k <= nums.length
Follow-up: Replace every number by its parity and this becomes 'count subarrays with sum k'.
Hints for Count Number of Nice Subarrays
Hint 1
The actual values do not matter — only whether each element is odd.
Hint 2
Map odd to 1 and even to 0; a nice subarray is one summing to
k.Hint 3
Then it is the standard prefix-count trick, seeded with
{0: 1}.
How to solve Count Number of Nice Subarrays
Only parity matters: map odd to 1 and even to 0, then count subarrays summing to k with the prefix-count trick.
Approach
- Maintain
count[oddPrefix]seeded with{0: 1}. - For each element, add
x % 2to the running odd count and addcount[odds - k]to the answer. - Increment
count[odds].
Why it works
A subarray has exactly k odds iff its two bounding prefixes differ by k in odd count, so the map lookup counts each nice subarray ending at the current index.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Use
x % 2, notx & 1, in languages where negative odd numbers produce-1under%— or takeabsfirst.
Reference solution
Python
def numberOfSubarrays(nums, k: int) -> int:
count = {0: 1}
odds = answer = 0
for x in nums:
odds += x % 2
answer += count.get(odds - k, 0)
count[odds] = count.get(odds, 0) + 1
return answerJava
public static int numberOfSubarrays(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1);
int odds = 0, total = 0;
for (int v : nums) {
odds += v % 2;
total += count.getOrDefault(odds - k, 0);
count.put(odds, count.getOrDefault(odds, 0) + 1);
}
return total;
}C++
int numberOfSubarrays(vector<int>& nums, int k) {
unordered_map<int, int> count;
count[0] = 1;
int odds = 0, total = 0;
for (int v : nums) {
odds += v % 2;
auto it = count.find(odds - k);
if (it != count.end()) total += it->second;
count[odds]++;
}
return total;
}JavaScript
var numberOfSubarrays = function(nums, k) {
const count = new Map();
count.set(0, 1);
let odds = 0, total = 0;
for (let i = 0; i < nums.length; i++) {
odds += nums[i] % 2;
total += count.get(odds - k) || 0;
count.set(odds, (count.get(odds) || 0) + 1);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets