Count Number of Nice Subarrays
Problem Description:
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.
Examples:
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].
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There are no odd numbers in the array.
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
Explanation: There are 16 subarrays containing exactly 2 odd numbers.
Constraints:
1 <= nums.length <= 5*10⁴
1 <= nums[i] <= 10⁵
1 <= k <= nums.length
Brute Force Approach:
When we read the problem statement, the first idea that comes to mind is simple:
We will iterate through each subarray, count the number of odd elements in it, and if the count of odd numbers equals k, we increment the answer.
How to do it?
We can use a brute-force solution by traversing through the array.
- Traverse through the array.
- For each element, iterate through all subarrays starting from that element and count the number of odd elements.
- If the count of odd elements equals k, increase the answer.
- Finally, return the answer.
Let's understand with an example:
Input: nums = [1, 1, 2, 1, 1], k = 3
- Start at index 0:
Subarray [1] → odd count = 1
Subarray [1, 1] → odd count = 2
Subarray [1, 1, 2] → odd count = 2
Subarray [1, 1, 2, 1] → odd count = 3 → answer += 1
Subarray [1, 1, 2, 1, 1] → odd count = 4 - Start at index 1:
Subarray [1] → odd count = 1
Subarray [1, 2] → odd count = 1
Subarray [1, 2, 1] → odd count = 2
Subarray [1, 2, 1, 1] → odd count = 3 → answer += 1 - Start at index 2:
Subarray [2] → odd count = 0
Subarray [2, 1] → odd count = 1
Subarray [2, 1, 1] → odd count = 2 - Start at index 3:
Subarray [1] → odd count = 1
Subarray [1, 1] → odd count = 2 - Start at index 4:
Subarray [1] → odd count = 1
Final Answer: 2
How to code it up?
- Initialize ans to 0 and n to the length of the array.
- Iterate through each starting index i from 0 to n-1.
- Set oddCount to 0 for each starting index.
- Iterate from j = i to n-1 to expand the subarray.
- If nums[j] is odd, increment oddCount.
- If oddCount == k, increment ans.
- After all iterations, return the value of ans.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
// Get the size of the input array
int n = nums.size();
// Initialize the answer to 0
int ans = 0;
// Outer loop: Iterate through each possible starting index of the subarray
for(int i = 0; i < n; i++) {
// Initialize the count of odd numbers in the current subarray to 0
int oddCount = 0;
// Inner loop: Iterate through each subarray starting at index i
for(int j = i; j < n; j++) {
// Check if the current number is odd
if(nums[j] % 2 == 1)
// Increment oddCount if the number is odd
oddCount++;
// If the number of odd numbers equals k, increment the answer
if(oddCount == k)
ans++;
}
}
// Return the final count of subarrays with exactly k odd numbers
return ans;
}
};2. Java Try on Compiler
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
// Get the size of the input array
int n = nums.length;
// Initialize the answer to 0
int ans = 0;
// Outer loop: Iterate through each possible starting index of the subarray
for (int i = 0; i < n; i++) {
// Initialize the count of odd numbers in the current subarray to 0
int oddCount = 0;
// Inner loop: Iterate through each subarray starting at index i
for (int j = i; j < n; j++) {
// Check if the current number is odd
if (nums[j] % 2 == 1)
// Increment oddCount if the number is odd
oddCount++;
// If the number of odd numbers equals k, increment the answer
if (oddCount == k)
ans++;
}
}
// Return the final count of subarrays with exactly k odd numbers
return ans;
}
}3. Python Try on Compiler
class Solution:
def numberOfSubarrays(self, nums, k):
# Get the size of the input array
n = len(nums)
# Initialize the answer to 0
ans = 0
# Outer loop: Iterate through each possible starting index of the subarray
for i in range(n):
# Initialize the count of odd numbers in the current subarray to 0
oddCount = 0
# Inner loop: Iterate through each subarray starting at index i
for j in range(i, n):
# Check if the current number is odd
if nums[j] % 2 == 1:
# Increment oddCount if the number is odd
oddCount += 1
# If the number of odd numbers equals k, increment the answer
if oddCount == k:
ans += 1
# Return the final count of subarrays with exactly k odd numbers
return ans
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numberOfSubarrays = function(nums, k) {
// Get the size of the input array
const n = nums.length;
// Initialize the answer to 0
let ans = 0;
// Outer loop: Iterate through each possible starting index of the subarray
for (let i = 0; i < n; i++) {
// Initialize the count of odd numbers in the current subarray to 0
let oddCount = 0;
// Inner loop: Iterate through each subarray starting at index i
for (let j = i; j < n; j++) {
// Check if the current number is odd
if (nums[j] % 2 === 1) {
// Increment oddCount if the number is odd
oddCount++;
}
// If the number of odd numbers equals k, increment the answer
if (oddCount === k) {
ans++;
}
}
}
// Return the final count of subarrays with exactly k odd numbers
return ans;
};Time Complexity: O(n²)
This approach runs two nested loops to find all subarrays, one inside another, where the outer loop runs n times
(i.e. i ranges from 0 to n), and for each iteration of the outer loop, the inner loop(i.e. j ranges from i to n) also runs n-i times.
Analyzing the Loops:
Outer Loop (indexed by i):
It runs from 0 to n-1. So, it iterates n times.
Inner Loop (indexed by j):
For each fixed i, j runs from i to n-1.
When i = 0, j runs n times.
When i = 1, j runs n-1 times.
When i = 2, j runs n-2 times.
…
When i = n-1, j runs 1 time.
Total Iterations:
To find the total number of iterations of the inner loop across all iterations of the outer loop,
we sum up the iterations for each value of i: ∑(i=0 to n−1) (n−i)
This is the sum of an arithmetic series: n+(n−1)+(n−2)+…+1.
If we closely observe and reverse the series
we get 1 + 2 + 3 + … + (n-2) + (n-1) + n.
That is nothing but the sum of n terms.
So the sum of n numbers from 1 to n is (n*(n+1))/2.
Thus, the total number of operations is (n*(n+1))/2.
Simplifying to Big-O Notation:
In Big-O notation, we focus on the term that grows the fastest as n increases, and we ignore constant factors and lower-order terms.
Therefore: O((n*(n+1))/2) ≈ O(n²)
Conclusion: The time complexity of the given code is O(n²).
This is because the nested loops result in a quadratic number of total operations, which dominate the runtime as the input size n becomes large.
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
The solution uses only a few variables (ans, oddCount) are used, which require O(1) space.
Total Space Complexity: O(n)
The input array nums is given, which requires O(n) space.
Adding this to the auxiliary space gives: Total Space = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the size of the array is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes, of course!
We can definitely optimize it—let's do it!
In the previous approach, we iterated through each element in the array and considered all possible subarrays starting from that element. For every subarray, we counted how many odd numbers were present. If the count of odd numbers in a subarray was equal to k, we incremented the answer. Finally, after checking all subarrays, we returned the answer.
Okay, so we know that in the previous approach, we iterated over each element and checked all subarrays starting from that element, counting all odd numbers. This process takes O(n²) complexity, and we need to optimize this part.
But how can we optimize this?
Alright, let's break the problem into two parts:
- We need to check if a number is odd or even.
- If the number is odd, check whether the number of odd elements in the subarray is equal to k or not.
Understood? Perfect.
Now, it's simple to check if a number is odd or not: we mod it by 2. If it's odd, the result will be 1; if it's even, it will be 0.
To make this simpler, we can replace each element in the array with 1 for odd numbers and 0 for even numbers, as we only care about the parity of the elements and not their actual values.
Great! Now our array contains 1 for odd elements and 0 for even elements.
Next, we need to figure out how many subarrays have exactly k odd elements. Since 1 represents odd elements, this boils down to finding how many subarrays have a sum equal to k.
Doesn’t this sound familiar now?
Yes! This is now a classic subarray sum equals k problem!
Okay, now let's figure out how to calculate the sum of any subarray in constant time.
Suppose we have an array nums, and we take two indices of this array, i and j, where i < j. If we want to calculate the sum of the subarray nums[i..j] in constant time, what can we do?
Let's compute the sum of all elements of nums up to index j and call it sumⱼ.
Similarly, compute the sum of all elements of nums up to index i - 1 and call it sumᵢ-₁.
Now, if we want the sum of the subarray between index i and j, we can simply compute:
sum of nums[i..j] = sumⱼ - sumᵢ-₁.
This is because subtracting the sum up to index i - 1 from the sum up to index j gives the sum of elements between i and j.
Now, if we know that the sum of the subarray nums[i..j] is equal to k, we can write:
k = sumⱼ - sumᵢ-₁
Rearranging this equation:
sumᵢ-₁ = sumⱼ - k
This means that if we are at any index j, and the value sumⱼ - k is equal to the sum of elements up to some earlier index i - 1, then there exists a subarray between i and j whose sum is exactly k.
How can we improve the lookup time for checking if a value has been encountered before?
Yes! by using a hashmap. The idea is simple:
- As we iterate through the array, we keep track of the running sum (sumⱼ).
- We can store all previously encountered sums in a hashmap. The key will be the sum value, and the value will be the count of how many times that sum has occurred.
- For each element at index j, we check if sumⱼ - k is present in the hashmap. If it is, it means there is a subarray ending at j that has exactly k odd elements.
- Using a hashmap, we can easily perform this lookup in O(1) time, making the process efficient.
This approach allows us to quickly check if a sum has been encountered and, if it has, determine how many subarrays end at the current index that satisfies the condition. The hashmap helps in reducing the need for a nested loop, improving performance.
Using this idea, we can count all subarrays whose sum equals k efficiently!
How to do it?
Here is the approach step by step:
- Change all odd elements in the array to 1 and even elements to 0.
- Traverse through the array while calculating the cumulative sum (prefix sum) at each index.
- Use a hashmap to store the frequency of these cumulative sums for faster lookup.
- For each index, check if sum - k exists in the hashmap. If it does, that means there is a subarray whose sum is k.
- Increment the result by the frequency of sum - k in the hashmap.
- Update the hashmap with the current cumulative sum.
- Finally, return the result.
Let's understand with an example:
Let's dry run on Input: nums = [1,1,2,1,1] and k = 3
- Convert nums: [1,1,2,1,1] → [1,1,0,1,1] (odd → 1, even → 0).
- Initialize sum = 0, count = 0, hashmap = {0: 1}
Iterate through the array:
- Index 0 (num = 1):
- sum = 1
- sum - k = -2 (not in hashmap).
- Update hashmap = {0: 1, 1: 1}
- Index 1 (num = 1):
- sum = 2
- sum - k = -1 (not in hashmap).
- Update hashmap = {0: 1, 1: 1, 2: 1}
- Index 2 (num = 0):
- sum = 2
- sum - k = -1 (not in hashmap).
- Update hashmap = {0: 1, 1: 1, 2: 2}
- Index 3 (num = 1):
- sum = 3
- sum - k = 0 (exists in hashmap, freq = 1).
- count = 1
- Update hashmap = {0: 1, 1: 1, 2: 2, 3: 1}
- Index 4 (num = 1):
- sum = 4
- sum - k = 1 (exists in hashmap, freq = 1).
- count = 2
- Update hashmap = {0: 1, 1: 1, 2: 2, 3: 1, 4: 1}
Final count = 2.
How to code it up:
Here are the steps to code it up:
- Convert all elements in the array to 1 if they are odd, and 0 if they are even.
- Initialize a hashmap to store the frequencies of prefix sums.
- Traverse through the array.
- Update the cumulative sum as you iterate.
- Check if (sum - k) exists in the hashmap.
- If it exists, add the frequency of (sum - k) from the hashmap to the answer.
- Update the frequency of the current cumulative sum in the hashmap.
- Return the total count of nice subarrays.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
// Get the size of the array
int n = nums.size();
// Convert all elements to 1 if odd, 0 if even
for(auto &num: nums)
num %= 2;
// Initialize a hashmap to store the prefix sum frequencies
unordered_map<int, int> mp;
// To handle the case when the prefix sum itself is equal to k
mp[0] = 1;
// Variable to store the cumulative sum
int sum = 0;
// Variable to store the count of nice subarrays
int ans = 0;
// Traverse through the array
for(int i = 0; i < n; i++) {
// Update the cumulative sum
sum += nums[i];
// Check if (sum - k) exists in the hashmap
if(mp.find(sum - k) != mp.end()) {
// Add the frequency of (sum - k) to the answer
ans += mp[sum - k];
}
// Update the frequency of the current sum in the hashmap
mp[sum]++;
}
// Return the total count of nice subarrays
return ans;
}
};
2. Java Try on Compiler
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
// Get the size of the array
int n = nums.length;
// Convert all elements to 1 if odd, 0 if even
for (int i = 0; i < n; i++) {
nums[i] %= 2;
}
// Initialize a hashmap to store the prefix sum frequencies
Map<Integer, Integer> map = new HashMap<>();
// To handle the case when the prefix sum itself is equal to k
map.put(0, 1);
// Variable to store the cumulative sum
int sum = 0;
// Variable to store the count of nice subarrays
int ans = 0;
// Traverse through the array
for (int i = 0; i < n; i++) {
// Update the cumulative sum
sum += nums[i];
// Check if (sum - k) exists in the hashmap
if (map.containsKey(sum - k)) {
// Add the frequency of (sum - k) to the answer
ans += map.get(sum - k);
}
// Update the frequency of the current sum in the hashmap
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
// Return the total count of nice subarrays
return ans;
}
}
3. Python Try on Compiler
class Solution:
def numberOfSubarrays(self, nums, k):
# Get the size of the array
n = len(nums)
# Convert all elements to 1 if odd, 0 if even
nums = [num % 2 for num in nums]
# Initialize a hashmap to store the prefix sum frequencies
prefix_sum = {0: 1} # To handle the case when the prefix sum itself is equal to k
# Variable to store the cumulative sum
sum_ = 0
# Variable to store the count of nice subarrays
ans = 0
# Traverse through the array
for num in nums:
# Update the cumulative sum
sum_ += num
# Check if (sum - k) exists in the hashmap
if (sum_ - k) in prefix_sum:
# Add the frequency of (sum - k) to the answer
ans += prefix_sum[sum_ - k]
# Update the frequency of the current sum in the hashmap
prefix_sum[sum_] = prefix_sum.get(sum_, 0) + 1
# Return the total count of nice subarrays
return ans
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numberOfSubarrays = function (nums, k) {
// Get the size of the array
let n = nums.length;
// Convert all elements to 1 if odd, 0 if even
for (let i = 0; i < n; i++) {
nums[i] %= 2;
}
// Initialize a hashmap to store the prefix sum frequencies
const map = new Map();
// To handle the case when the prefix sum itself is equal to k
map.set(0, 1);
// Variable to store the cumulative sum
let sum = 0;
// Variable to store the count of nice subarrays
let ans = 0;
// Traverse through the array
for (let i = 0; i < n; i++) {
// Update the cumulative sum
sum += nums[i];
// Check if (sum - k) exists in the hashmap
if (map.has(sum - k)) {
// Add the frequency of (sum - k) to the answer
ans += map.get(sum - k);
}
// Update the frequency of the current sum in the hashmap
map.set(sum, (map.get(sum) || 0) + 1);
}
// Return the total count of nice subarrays
return ans;
};Time Complexity: O(n)
The solution iterates over the array once to compute the prefix sum, which takes O(n) time.
For each element, we check if (sum - k) exists in the hashmap and update the hashmap with the current prefix sum.
Both of these operations (checking and updating) take O(1) time on average due to the efficient implementation of hashmaps (or dictionaries in Python and JavaScript).
Thus, the overall time complexity is dominated by the single traversal through the array and the constant time operations with the hashmap, leading to an overall time complexity of O(n).
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
The auxiliary space is the extra space used by the algorithm, excluding the input array. In this case, the main extra space is used by the hashmap, which stores the prefix sums and their frequencies.
In the worst case, if the array contains all distinct prefix sums, the hashmap will store n entries, leading to O(n) auxiliary space. - Total Space Complexity: O(n)
The total space accounts for both the input array and the additional space used during execution.
Thus, the total space complexity is O(n).
Can there be any other approach?
Yes, there is another approach to solve this problem.
We need to find the number of subarrays with exactly k odd elements. We know that a subarray is a contiguous part of an array. So, can we take a window in the array where the number of odd elements in the window is equal to k and then adjust the window to find all nice subarrays?
Well, yes, but the problem is that we don't know on what basis we should shrink or expand the window. This makes it hard to determine when to shrink or expand the window in order to go through all the nice subarrays.
To solve this problem, we can break it down further. We can easily find all the subarrays with number of odd elements less than or equal to k by maintaining a window. So, we count all subarrays with number of odd elements less than or equal to k.
Then, using the same technique, we can find the count of subarrays with number of odd elements less than or equal to (k-1) and subtract it from the count of subarrays with number of odd elements less than or equal to k.
In other words, we can represent it as:
Count of subarrays with k odd elements =
Count of subarrays with less than or equal to k odd elements -
Count of subarrays with less than or equal to (k-1) odd elements.
By doing this, we can solve the problem efficiently.
How to do it?
Here’s the step-by-step approach to solve the problem:
- Calculate the number of subarrays with odd elements less than or equal to k:
Maintain a sliding window with at most k odd elements.
If the number of odd elements exceeds k, shrink the window from the left.
Count all subarrays within the window that satisfy this condition. - Calculate the number of subarrays with odd elements less than or equal to (k-1):
Repeat the same process as in step 1, but now with at most k-1 odd elements in the window. - Calculate the difference:
The result is the difference between the number of subarrays with at most k odd elements and the number of subarrays with at most (k-1) odd elements. - Return the difference:
This difference gives the count of subarrays with exactly k odd elements.
Let's understand with and example:
Here’s the concise dry run for nums = [1, 1, 2, 1, 1] and k = 3, with all the subarrays mentioned:
Step 1: Count subarrays with at most k = 3 odd elements
- Subarrays with at most 3 odd elements:Total = 8 subarrays
- [1]
- [1, 1]
- [1, 1, 2]
- [1, 1, 2, 1]
- [1, 1, 2, 1, 1]
- [1, 2]
- [1, 2, 1]
- [2, 1]
- [2, 1, 1]
- [1, 1]
- [1, 2]
- [1, 1]
Step 2: Count subarrays with at most k-1 = 2 odd elements
- Subarrays with at most 2 odd elements:Total = 6 subarrays
- [1]
- [1, 1]
- [1, 1, 2]
- [1, 1, 2, 1]
- [1, 1]
- [1, 2]
- [2, 1]
Step 3: Calculate the difference
- Subarrays with exactly 3 odd elements =
Subarrays with at most 3 odd elements - Subarrays with at most 2 odd elements = 8 - 6 = 2.
Final Output: 2
The two subarrays with exactly 3 odd elements are:
- [1, 1, 2, 1]
- [1, 2, 1, 1]
So, the final count of subarrays with exactly 3 odd elements is 2.
How to code it up:
Here are the concise steps to code up the solution:
Define a helper function (solve):
- Initialize i, oddCount, and ans to 0.
- Traverse through the array using index j.
- If nums[j] is odd, increment oddCount.
- While oddCount > k, move i to the right and decrement oddCount for every odd number at nums[i].
- Add the count of subarrays from index i to j to ans (i.e., ans += (j - i + 1)).
Main function (numberOfSubarrays):
- Use the solve function to count subarrays with at most k odd elements.
- Subtract the result of solve(nums, k-1) from solve(nums, k) to get the subarrays with exactly k odd elements.
Return the result: The difference will give the count of subarrays with exactly k odd elements.
Code Implementation
1. C++ Try on Compiler
class Solution {
// Helper function to count subarrays with at most k odd elements
int solve(vector<int> &nums, int k) {
// Left pointer of the sliding window
int i = 0;
// Count of odd numbers in the current window
int oddCount = 0;
// Variable to store the count of subarrays
int ans = 0;
// Traverse through the array using the right pointer (j)
for (int j = 0; j < nums.size(); j++) {
// If the current element is odd, increment oddCount
if (nums[j] % 2 != 0) {
oddCount++;
}
// If oddCount exceeds k, shrink the window from the left
while (oddCount > k) {
// If the element at the left pointer is odd, decrement oddCount
if (nums[i] % 2 != 0) {
oddCount--;
}
// Move the left pointer to the right
i++;
}
// Add the number of subarrays ending at index j to the answer
ans += (j - i + 1);
}
// Return the total count of subarrays with at most k odd elements
return ans;
}
public:
// Main function to count subarrays with exactly k odd elements
int numberOfSubarrays(vector<int>& nums, int k) {
// Subtract the count of subarrays with at most k-1 odd elements from
// the count of subarrays with at most k odd elements to get the exact
// count of subarrays with exactly k odd elements
return solve(nums, k) - solve(nums, k - 1);
}
};
2. Java Try on Compiler
class Solution {
// Helper function to count subarrays with at most k odd elements
public int solve(int[] nums, int k) {
// Left pointer of the sliding window
int i = 0;
// Count of odd numbers in the current window
int oddCount = 0;
// Variable to store the count of subarrays
int ans = 0;
// Traverse through the array using the right pointer (j)
for (int j = 0; j < nums.length; j++) {
// If the current element is odd, increment oddCount
if (nums[j] % 2 != 0) {
oddCount++;
}
// If oddCount exceeds k, shrink the window from the left
while (oddCount > k) {
// If the element at the left pointer is odd, decrement oddCount
if (nums[i] % 2 != 0) {
oddCount--;
}
// Move the left pointer to the right
i++;
}
// Add the number of subarrays ending at index j to the answer
ans += (j - i + 1);
}
// Return the total count of subarrays with at most k odd elements
return ans;
}
// Main function to count subarrays with exactly k odd elements
public int numberOfSubarrays(int[] nums, int k) {
// Subtract the count of subarrays with at most k-1 odd elements from
// the count of subarrays with at most k odd elements to get the exact
// count of subarrays with exactly k odd elements
return solve(nums, k) - solve(nums, k - 1);
}
}
3. Python Try on Compiler
class Solution:
# Helper function to count subarrays with at most k odd elements
def solve(self, nums, k):
# Left pointer of the sliding window
i = 0
# Count of odd numbers in the current window
oddCount = 0
# Variable to store the count of subarrays
ans = 0
# Traverse through the array using the right pointer (j)
for j in range(len(nums)):
# If the current element is odd, increment oddCount
if nums[j] % 2 != 0:
oddCount += 1
# If oddCount exceeds k, shrink the window from the left
while oddCount > k:
# If the element at the left pointer is odd, decrement oddCount
if nums[i] % 2 != 0:
oddCount -= 1
# Move the left pointer to the right
i += 1
# Add the number of subarrays ending at index j to the answer
ans += (j - i + 1)
# Return the total count of subarrays with at most k odd elements
return ans
# Main function to count subarrays with exactly k odd elements
def numberOfSubarrays(self, nums, k):
# Subtract the count of subarrays with at most k-1 odd elements from
# the count of subarrays with at most k odd elements to get the exact
# count of subarrays with exactly k odd elements
return self.solve(nums, k) - self.solve(nums, k - 1)
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// Helper function to count subarrays with at most k odd elements
var solve = function (nums, k) {
// Left pointer of the sliding window
let i = 0;
// Count of odd numbers in the current window
let oddCount = 0;
// Variable to store the count of subarrays
let ans = 0;
// Traverse through the array using the right pointer (j)
for (let j = 0; j < nums.length; j++) {
// If the current element is odd, increment oddCount
if (nums[j] % 2 !== 0) {
oddCount++;
}
// If oddCount exceeds k, shrink the window from the left
while (oddCount > k) {
// If the element at the left pointer is odd, decrement oddCount
if (nums[i] % 2 !== 0) {
oddCount--;
}
// Move the left pointer to the right
i++;
}
// Add the number of subarrays ending at index j to the answer
ans += (j - i + 1);
}
// Return the total count of subarrays with at most k odd elements
return ans;
};
var numberOfSubarrays = function (nums, k) {
// Subtract the count of subarrays with at most k-1 odd elements from
// the count of subarrays with at most k odd elements to get the exact
// count of subarrays with exactly k odd elements
return solve(nums, k) - solve(nums, k - 1);
};
Time Complexity: O(n)
Helper Function solve:
- The solve function traverses the array using the right pointer j from 0 to n-1, where n is the length of the nums array.
- For each element at j, the while loop is used to shrink the window from the left pointer i when the count of odd elements exceeds k.
- The while loop may increment i multiple times, but each element is processed at most once by both i and j. Therefore, the total number of iterations of the while loop across the entire execution of solve is bounded by n.
Total time complexity of solve is O(n), where n is the length of the array.
Function numberOfSubarrays:
- The numberOfSubarrays function calls the solve function twice: once with k and once with k - 1.
- Each call to solve has a time complexity of O(n).
Therefore, the total time complexity of the numberOfSubarrays function is: O(n) + O(n) = O(n).
Space Complexity: O(n)
- Auxiliary Space Complexity: O(1)
In this solution, the only additional space used is for the sliding window which keeps track of the left pointer i, the count of odd elements oddCount, and the result ans.
The solve function also uses a few integer variables (i, oddCount, ans, j) to track the current state, but no extra data structures like arrays or hashmaps are required, so the auxiliary space is O(1). - Total Space Complexity: O(n)
The input array nums already occupies O(n) space.
Thus, the total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.