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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 value 1 indicates that there's one way to have zero odd numbers so far (essentially, the subarray of length zero).
Initialize two variables, ans and t to 0. ans will hold the final count of nice subarrays, while t will keep the running count of odd numbers seen.
Loop through each number v in the array nums.

a. Use the bitwise AND operation (v & 1) to determine if v is odd. If so, add 1 to t. The operation v & 1 evaluates to 1 if v is odd, and 0 if v is even.

b. Calculate t - k, which represents the prefix sum we'd have if we subtracted k odd numbers from the current count. If this value has been seen before (which means there's a subarray ending at an earlier position with t - k odd numbers), we can form a nice subarray ending at the current index. Add the count of t - k from the Counter to ans.

c. Increment the count of t in the Counter by 1 to indicate that we have encountered another subarray ending at the current index with a prefix sum of t 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 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example 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 and t to 0. ans will count our nice subarrays, and t will hold our running tally of odd numbers seen.
We start iterating through each number v in nums.
- For v = 1: It's odd (since 1 & 1 is 1), so we increment t to 1. We then look for t - k, which is -1. Since -1 is not in our counter, there are 0 subarrays ending here with 2 odd numbers. We update the counter to {0: 1, 1: 1}.
- For v = 2: It's even (since 2 & 1 is 0), so t remains 1. Looking for t - k (1-2=-1) yields 0 subarrays. Our counter doesn't change.
- For v = 3: It's odd, t becomes 2. Now, t - k is 0, and since our counter shows {0: 1}, there is 1 subarray ending here with exactly 2 odd numbers. We increment ans to 1 and update the counter to {0: 1, 1: 1, 2: 1}.
- For v = 4: It's even, so t stays 2. We look for t - k (2-2=0) in the counter, find 1 occurrence, so there's 1 more subarray that meets the criteria. Increment ans to 2, and the counter remains the same.
- For v = 5: Again, it's odd, t increases to 3. Looking for t - k (3-2=1), we find 1 in the counter. This gives us 1 subarray. ans goes up to 3, and we update the counter to {0: 1, 1: 1, 2: 1, 3: 1}.
After iterating through the array, we have ans as 3, meaning there are three subarrays within nums 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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know