1248. Count Number of Nice Subarrays
Problem Description
The problem provides us with an array nums
of integers and an integer k
. We need to count how many continuous subarrays (a sequence of adjacent elements in the array) have exactly k
odd numbers. These subarrays are referred to as nice subarrays.
The main challenge is to do this efficiently for possibly large arrays.
Intuition
To solve this problem, we can apply the concept of prefix sums; however, instead of keeping a running total of the elements, we'll keep a running count of how many odd numbers we've encountered so far. The key idea is to use a map (Counter
in Python) to keep track of how many times each count of odd numbers has occurred in our running total (prefix).
Let's say we're iterating through the array and at some point we have encountered x
odd numbers. Now, if at an earlier point in the array we had encountered x - k
odd numbers, any subarray starting from that earlier point to our current position will have exactly k
odd numbers. Why? Because x - (x - k) = k
.
So, we use a counter to keep track of all previously seen counts of odd numbers. Every time we hit a new odd number, we increment our current count (t
in the code). We then check in our counter to see how many times we've previously seen a count of t - k
. The value we get tells us the number of subarrays ending at the current position with exactly k
odd numbers.
We add this count to our answer (ans
in the code) and move to the next element. Since the subarrays are continuous, we increment our counter for the current count of odd numbers to reflect that we found a new subarray starting point that ends at the current index.
The Counter
is initialized with {0: 1}
to handle the case where the first k
elements form a nice subarray. The count is zero (no odd numbers yet), but we consider it as a valid starting point.
The solution iteratively applies the above logic, using bitwise operations to check if a number is odd (v & 1
) and updating the count and answer accordingly.
Learn more about Math and Sliding Window patterns.
Solution Approach
The solution uses a Counter
dictionary to store the frequency of counts of odd numbers encountered as a prefix sum. This Counter
represents how many times each count has been seen so far in the array, which is essential for determining the number of nice subarrays.
Here's a step-by-step breakdown of the implementation:
-
Initialize a
Counter
with{0: 1}
. This accounts for the prefix sum before we start traversing the array. The value1
indicates that there's one way to have zero odd numbers so far (essentially, the subarray of length zero). -
Initialize two variables,
ans
andt
to0
.ans
will hold the final count of nice subarrays, whilet
will keep the running count of odd numbers seen. -
Loop through each number
v
in the arraynums
.a. Use the bitwise AND operation (
v & 1
) to determine ifv
is odd. If so, add1
tot
. The operationv & 1
evaluates to1
ifv
is odd, and0
ifv
is even.b. Calculate
t - k
, which represents the prefix sum we'd have if we subtractedk
odd numbers from the current count. If this value has been seen before (which means there's a subarray ending at an earlier position witht - k
odd numbers), we can form a nice subarray ending at the current index. Add the count oft - k
from theCounter
toans
.c. Increment the count of
t
in theCounter
by1
to indicate that we have encountered another subarray ending at the current index with a prefix sum oft
odd numbers. -
After the loop completes,
ans
holds the total count of nice subarrays, and this is what is returned.
Here is how the algorithm works in a nutshell: By maintaining a running count of odd numbers, and having a Counter
to record how many times each count has occurred, we can efficiently compute how many subarrays end at a particular index with exactly k
odd numbers. This lets us add up the counts for all subarrays in the array just by iterating through it once.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example where nums = [1, 2, 3, 4, 5]
and k = 2
. We want to find out how many continuous subarrays have exactly 2 odd numbers.
Following the solution approach:
-
We initialize a
Counter
with{0: 1}
to count the number of times we have encountered 0 odd numbers so far (which is once for the empty subarray). -
We set
ans
andt
to0
.ans
will count our nice subarrays, andt
will hold our running tally of odd numbers seen. -
We start iterating through each number
v
innums
.-
For
v = 1
: It's odd (since1 & 1
is1
), so we incrementt
to1
. We then look fort - k
, which is-1
. Since-1
is not in our counter, there are0
subarrays ending here with 2 odd numbers. We update the counter to{0: 1, 1: 1}
. -
For
v = 2
: It's even (since2 & 1
is0
), sot
remains1
. Looking fort - k
(1-2=-1
) yields0
subarrays. Our counter doesn't change. -
For
v = 3
: It's odd,t
becomes2
. Now,t - k
is0
, and since our counter shows{0: 1}
, there is1
subarray ending here with exactly 2 odd numbers. We incrementans
to1
and update the counter to{0: 1, 1: 1, 2: 1}
. -
For
v = 4
: It's even, sot
stays2
. We look fort - k
(2-2=0
) in the counter, find1
occurrence, so there's1
more subarray that meets the criteria. Incrementans
to2
, and the counter remains the same. -
For
v = 5
: Again, it's odd,t
increases to3
. Looking fort - k
(3-2=1
), we find1
in the counter. This gives us1
subarray.ans
goes up to3
, and we update the counter to{0: 1, 1: 1, 2: 1, 3: 1}
.
-
-
After iterating through the array, we have
ans
as3
, meaning there are three subarrays withinnums
that contain exactly 2 odd numbers. These subarrays are[1, 2, 3]
,[3, 4]
, and[5]
.
So the function would return 3
as the result. The efficiency of the solution stems from the fact that we only needed to traverse the array once and keep a running tally of our counts in the Counter
, which gives us the ability to find the number of nice subarrays in constant time for each element of the array.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def numberOfSubarrays(self, nums: List[int], k: int) -> int:
5 # Initialize counter for odd counts with 0 count as 1 (base case)
6 odd_count = Counter({0: 1})
7
8 # Initialize variables for the answer and the temporary count of odds
9 answer = temp_odd_count = 0
10
11 # Iterate over each value in the list
12 for value in nums:
13 # Increment temp_odd_count if value is odd
14 temp_odd_count += value & 1 # value & 1 is 1 if value is odd, 0 otherwise
15
16 # If there are at least k odd numbers, add the count to answer
17 # This checks if a valid subarray ending at the current index exists
18 answer += odd_count[temp_odd_count - k]
19
20 # Increment the count of the current number of odd integers seen so far
21 odd_count[temp_odd_count] += 1
22
23 # Return the total number of valid subarrays
24 return answer
25
1class Solution {
2 public int numberOfSubarrays(int[] nums, int k) {
3 int n = nums.length; // Length of the input array
4 int[] prefixOddCount = new int[n + 1]; // Array to keep track of the prefix sums of odd numbers
5 prefixOddCount[0] = 1; // There's one way to have zero odd numbers - by taking no elements
6 int result = 0; // Initialize the result count to 0
7 int currentOddCount = 0; // Tracks the current number of odd elements encountered
8
9 // Iterate over each number in the input array
10 for (int num : nums) {
11 // If 'num' is odd, increment the count of odd numbers encountered so far
12 currentOddCount += num & 1;
13
14 // If we have found at least 'k' odd numbers so far
15 if (currentOddCount - k >= 0) {
16 // Add to 'result' the number of subarrays that have 'k' odd numbers up to this point
17 result += prefixOddCount[currentOddCount - k];
18 }
19
20 // Increment the count in our prefix sum array for the current odd count
21 prefixOddCount[currentOddCount]++;
22 }
23 return result; // Return the total count of subarrays with exactly 'k' odd numbers
24 }
25}
26
1#include <vector>
2
3class Solution {
4public:
5 int numberOfSubarrays(std::vector<int>& nums, int k) {
6 int size = nums.size(); // Store the size of the input vector nums
7 std::vector<int> count(size + 1, 0); // Vector to store the count of odd numbers
8 count[0] = 1; // There's one way to have zero odd numbers - empty subarray
9
10 int answer = 0; // Initialize the count of valid subarrays
11 int oddCount = 0; // Counter for the number of odd numbers in the current sequence
12
13 // Iterate through the input numbers
14 for (int num : nums) {
15 oddCount += num & 1; // Increment the odd count if num is odd
16 // If there have been at least k odd numbers so far, update the answer
17 if (oddCount >= k) {
18 answer += count[oddCount - k];
19 }
20 count[oddCount]++; // Increment the count for this number of odd numbers
21 }
22
23 return answer; // Return the total number of valid subarrays
24 }
25};
26
1function numberOfSubarrays(nums: number[], k: number): number {
2 // The length of the input array.
3 const arrayLength = nums.length;
4
5 // An array to store the count of subarrays with odd numbers sum.
6 const countOfSubarrays = new Array(arrayLength + 1).fill(0);
7
8 // Base condition: There is always 1 subarray with 0 odd numbers (the empty subarray).
9 countOfSubarrays[0] = 1;
10
11 // The answer to return that accumulates the number of valid subarrays.
12 let numberOfValidSubarrays = 0;
13
14 // Tracks the total number of odd numbers encountered so far.
15 let totalOdds = 0;
16
17 // Iterate through all elements in the array.
18 for (const value of nums) {
19 // If value is odd, increment the count of totalOdds.
20 totalOdds += value & 1;
21
22 // If there are enough previous odds to form a valid subarray, increment the count.
23 if (totalOdds - k >= 0) {
24 numberOfValidSubarrays += countOfSubarrays[totalOdds - k];
25 }
26
27 // Increment the count of subarrays we've seen with the current totalOdds.
28 countOfSubarrays[totalOdds] += 1;
29 }
30
31 // Return the total number of valid subarrays found.
32 return numberOfValidSubarrays;
33}
34
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the number of elements in the nums
list. This is because the code iterates through each element of the array exactly once.
During this iteration, the code performs constant-time operations: using bitwise AND to determine the parity of the number, updating the count hashtable, and incrementing the result. The lookup and update of the counter cnt
are also expected to be constant time because it is a hashtable.
The space complexity of the code is O(n)
. In the worst case, if all elements in nums
are odd, then the counter cnt
can potentially have as many entries as there are elements in nums
. Therefore, the size of the counter scales linearly with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!