I solved a coding challenge "Given an array of numbers, find number of subarrays that contain EXACTLY k odd numbers" by prefix sum as below:
int numberOfSubarrays(vector<int>& nums, int k) {
int total = 0;
int ans = 0;
std::vector<int> prefixSum{ 1 };
for ( int num : nums ) {
if ( num % 2 != 0 ) {
total += 1;
prefixSum.push_back( 1 );
} else {
prefixSum[prefixSum.size() - 1] += 1;
}
if ( total - k < prefixSum.size() ) {
ans += prefixSum[total - k];
}
}
return ans;
}
I then get a follow-up variation of it: "Given an array of numbers, find number of subarrays that contain AT MOST k odd numbers", and the time complexity is required to be same, i.e., O(n), so naturally I turned to prefix sum again, but I found it hard to copy the same solution to this variation.
Could someone teach me if this "AT MOST" version is solvable by prefix sum, how?
N.B. I know there are some discussions on similar challenge but the subarrays are required to be distinct in terms of elements. The regulation doesn't apply here, as long as starting and ending indices are different, subarray is considered distinct, e.g., array[1:3] is different than array[2:4] no matter how their elements are same or not.
I solved a coding challenge "Given an array of numbers, find number of subarrays that contain EXACTLY k odd numbers" by prefix sum as below:
int numberOfSubarrays(vector<int>& nums, int k) {
int total = 0;
int ans = 0;
std::vector<int> prefixSum{ 1 };
for ( int num : nums ) {
if ( num % 2 != 0 ) {
total += 1;
prefixSum.push_back( 1 );
} else {
prefixSum[prefixSum.size() - 1] += 1;
}
if ( total - k < prefixSum.size() ) {
ans += prefixSum[total - k];
}
}
return ans;
}
I then get a follow-up variation of it: "Given an array of numbers, find number of subarrays that contain AT MOST k odd numbers", and the time complexity is required to be same, i.e., O(n), so naturally I turned to prefix sum again, but I found it hard to copy the same solution to this variation.
Could someone teach me if this "AT MOST" version is solvable by prefix sum, how?
N.B. I know there are some discussions on similar challenge but the subarrays are required to be distinct in terms of elements. The regulation doesn't apply here, as long as starting and ending indices are different, subarray is considered distinct, e.g., array[1:3] is different than array[2:4] no matter how their elements are same or not.
Share Improve this question asked Feb 17 at 12:09 LindaLinda 18712 bronze badges1 Answer
Reset to default 3Not exactly prefix sum, but the idea is similar.
Your prefix sum solution effectively stores how many even numbers are there between each odd numbers. It does not apply to the revised "at most" scenario as it leads to overcounting.
Instead, you could store the index of each odd number, by which you get to count how many subarrays are there that ends with each number by a time complexity of O(n), as you wanted.
Taking nums = [8, 3, 6, 5, 2, 7], k = 2, as an example. For num[0], there is only one subarray [8] that ends with it, for sure it contains less than 1 odd number. For num[1], there are [8, 3], [3], etc. For nums[5], there are [6, 5, 2, 7], [5, 2, 7], [2, 7], [7].
Now hopefully you have caught the idea: For each number indexed at i, denoting the total odd numbers we have seen so far as total, and indices of each odd number as oddNumIndices, then:
If
total <= k, there are exactlyi - oddNumIndices[0]subarrays, whereoddNumIndices[0]is initialized to -1 so as to avoiding special handing on boundary.If
total > k, there are exactlyi - oddNumIndices[total - k]subarrays.
Also note that empty subarray [] is also valid for every k, so you need to add 1 to the final answer.
def myFunc( nums, k ):
total = 0
ans = 1 # [] contains odd numbers less than k for every k
oddNumIndices = [-1]
for i, num in enumerate( nums ):
if num % 2 != 0:
oddNumIndices.append( i )
total += 1
if total <= k:
ans += i - oddNumIndices[0]
else:
ans += i - oddNumIndices[total - k]
return ans