Leetcode 1248: Count Number of Nice Subarrays
You are given an array of integers nums and an integer k. A subarray is considered ’nice’ if it contains exactly k odd numbers. Your task is to return the number of nice subarrays in the given array.
Problem
Approach
Steps
Complexity
Input: You are given an array nums of integers and an integer k.
Example: nums = [1, 1, 2, 1, 1], k = 3
Constraints:
• 1 <= nums.length <= 50000
• 1 <= nums[i] <= 10^5
• 1 <= k <= nums.length
Output: Return the number of nice subarrays that contain exactly k odd numbers.
Example: 2
Constraints:
• Return 0 if no nice subarrays exist.
Goal: Find the number of subarrays with exactly k odd numbers.
Steps:
• Use a sliding window technique to count the number of subarrays with at most k odd numbers.
• The result is the difference between the number of subarrays with at most k odd numbers and those with at most k-1 odd numbers.
Goal: The array length is bounded and the elements of the array are positive integers.
Steps:
• 1 <= nums.length <= 50000
• 1 <= nums[i] <= 10^5
• 1 <= k <= nums.length
Assumptions:
• The array has at least 1 element and contains only integers.
• Input: nums = [1, 1, 2, 1, 1], k = 3
• Explanation: The subarrays with exactly 3 odd numbers are [1, 1, 2, 1] and [1, 2, 1, 1], so the result is 2.
Approach: To solve this problem efficiently, we use a sliding window approach to count the number of subarrays with exactly k odd numbers.
Observations:
• The problem can be broken down into counting subarrays with at most k odd numbers and using this to calculate the result.
• We can calculate the number of subarrays with at most k odd numbers by maintaining a window and counting the odd numbers in the window.
Steps:
• Define a helper function atmost(nums, k) to count the subarrays with at most k odd numbers.
• The sliding window technique is used to maintain the count of odd numbers in the current window.
• The final result is the difference between the number of subarrays with at most k odd numbers and those with at most k-1 odd numbers.
Empty Inputs:
• If the array is empty, return 0.
Large Inputs:
• The solution should efficiently handle arrays of size up to 50,000.
Special Values:
• If k is larger than the number of odd numbers in the array, return 0.
Constraints:
• Ensure the solution works for large inputs and edge cases such as all numbers being even or odd.
int numberOfSubarrays(vector<int>& nums, int k) {
return atmost(nums, k) - atmost(nums, k - 1);
}
int atmost(vector<int> &nums, int k) {
int cnt[2] = {};
int res = 0, j = 0;
for(int i = 0; i < nums.size(); i++) {
cnt[nums[i]%2]++;
while(cnt[1] > k) {
cnt[nums[j]%2]--;
j++;
}
res += (i - j + 1);
}
return res;
}
1 : Function Definition
int numberOfSubarrays(vector<int>& nums, int k) {
This function is defined to count the number of subarrays with at most `k` odd numbers. It takes a vector `nums` and an integer `k` as inputs.
2 : Return Statement
return atmost(nums, k) - atmost(nums, k - 1);
The result is calculated by subtracting the result of calling `atmost(nums, k-1)` from `atmost(nums, k)`. This gives the number of subarrays with exactly `k` odd numbers.
3 : Helper Function Definition
int atmost(vector<int> &nums, int k) {
This helper function counts the number of subarrays with at most `k` odd numbers using a sliding window technique.
4 : Variable Initialization
int cnt[2] = {};
The `cnt` array is initialized to track the counts of even and odd numbers in the current sliding window. `cnt[0]` tracks even numbers and `cnt[1]` tracks odd numbers.
5 : Variable Initialization
int res = 0, j = 0;
The variable `res` is initialized to count the total number of subarrays, and `j` is the left pointer for the sliding window.
6 : Loop Through Array
for(int i = 0; i < nums.size(); i++) {
A loop is used to iterate through the elements of `nums` using the index `i` as the right pointer of the sliding window.
7 : Update Count
cnt[nums[i]%2]++;
The count of either even or odd numbers is updated in the `cnt` array based on the current element in `nums`. If `nums[i]` is odd, `cnt[1]` is incremented.
8 : Adjust Sliding Window
while(cnt[1] > k) {
If the number of odd numbers in the current window exceeds `k`, the left pointer `j` is moved to the right to shrink the window until there are at most `k` odd numbers.
9 : Adjust Sliding Window
cnt[nums[j]%2]--;
The count of the element at the left pointer `j` is decremented, and the window is adjusted by moving `j` to the right.
10 : Adjust Sliding Window
j++;
Increment the left pointer `j` to shrink the window from the left side.
11 : Update Result
res += (i - j + 1);
Add the number of subarrays with at most `k` odd numbers in the current window to the result. The number of such subarrays is `(i - j + 1)`.
12 : Return Statement
return res;
Return the total number of subarrays with at most `k` odd numbers.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, O(n), where n is the length of the array.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, O(1), as we only use a few extra variables.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus