Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1248.html
1248. Count Number of Nice Subarrays (Medium)
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.
Example 1:
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].
Example 2:
Input: nums = [2,4,6], k = 1 Output: 0 Explanation: There is no odd numbers in the array.
Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2 Output: 16
Constraints:
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
Related Topics: Two Pointers
Solution 1. Map
Use a map m to store the mapping from the count of odd numbers cnt to the first index in the array that has cnt numbers in front of it and including itself.
When cnt >= k, we add m[cnt - k + 1] - m[cnt - k] to the answer.
// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int numberOfSubarrays(vector<int>& A, int k) {
int N = A.size(), cnt = 0, ans = 0;
unordered_map<int, int> m{ {0,-1} };
for (int i = 0; i < N; ++i) {
cnt += A[i] % 2;
if (m.count(cnt) == 0) m[cnt] = i;
if (cnt >= k) ans += m[cnt - k + 1] - m[cnt - k];
}
return ans;
}
};
Solution 2. Two Pointers
Assume the current pointer is j and the corresponding odd number count is cj, we need two pointers to get the answer.
The first pointer i is the index whose corresponding odd number count is cj - k + 1.
The second pointer prev is the index whose corresponding odd number count is cj - k.
So when cj >= k, we add i - prev to the answer.
// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numberOfSubarrays(vector<int>& A, int k) {
int N = A.size(), i = 0, j = 0, prev = -1, ans = 0, ci = 0, cj = 0;
while (j < N) {
cj += A[j++] % 2;
if (ci <= cj - k) {
prev = i;
while (ci <= cj - k) ci += A[i++] % 2;
}
if (cj >= k) ans += i - prev;
}
return ans;
}
};
Or use a single count.
// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numberOfSubarrays(vector<int>& A, int k) {
int N = A.size(), i = 0, j = 0, prev = -1, ans = 0, cnt = 0;
while (j < N) {
int c = A[j++] % 2;
cnt += c;
if (c && cnt >= k) {
prev = i;
while (A[i] % 2 == 0) ++i;
++i;
}
if (cnt >= k) ans += i - prev;
}
return ans;
}
};
Solution 3. At Most
Exactly k times = At Most k times - At Most k - 1 times.
// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419378/JavaC%2B%2BPython-Sliding-Window-O(1)-Space
class Solution {
int atMost(vector<int> &A, int k) {
int N = A.size(), i = 0, ans = 0;
for (int j = 0; j < N; ++j) {
k -= A[j] % 2;
while (k < 0) k += A[i++] % 2;
ans += j - i;
}
return ans;
}
public:
int numberOfSubarrays(vector<int>& A, int k) {
return atMost(A, k) - atMost(A, k - 1);
}
};
-
class Solution { public int numberOfSubarrays(int[] nums, int k) { List<Integer> oddIndices = new ArrayList<Integer>(); oddIndices.add(-1); int length = nums.length; for (int i = 0; i < length; i++) { if (nums[i] % 2 != 0) oddIndices.add(i); } oddIndices.add(length); int count = 0; int oddIndicesSize = oddIndices.size() - 2; int start = 1, end = oddIndicesSize - k + 1; for (int low = start; low <= end; low++) { int high = low + k - 1; int indexLow = oddIndices.get(low), indexHigh = oddIndices.get(high); int indexPrev = oddIndices.get(low - 1), indexNext = oddIndices.get(high + 1); count += (indexLow - indexPrev) * (indexNext - indexHigh); } return count; } } ############ class Solution { public int numberOfSubarrays(int[] nums, int k) { int n = nums.length; int[] cnt = new int[n + 1]; cnt[0] = 1; int ans = 0, t = 0; for (int v : nums) { t += v & 1; if (t - k >= 0) { ans += cnt[t - k]; } cnt[t]++; } return ans; } } -
// OJ: https://leetcode.com/problems/count-number-of-nice-subarrays/ // Time: O(N) // Space: O(N) class Solution { public: int numberOfSubarrays(vector<int>& A, int k) { int N = A.size(), cnt = 0, ans = 0; unordered_map<int, int> m{ {0,-1} }; for (int i = 0; i < N; ++i) { cnt += A[i] % 2; if (m.count(cnt) == 0) m[cnt] = i; if (cnt >= k) ans += m[cnt - k + 1] - m[cnt - k]; } return ans; } }; -
class Solution: def numberOfSubarrays(self, nums: List[int], k: int) -> int: cnt = Counter({0: 1}) ans = t = 0 for v in nums: t += v & 1 ans += cnt[t - k] cnt[t] += 1 return ans ############ # 1248. Count Number of Nice Subarrays # https://leetcode.com/problems/count-number-of-nice-subarrays/ class Solution: def numberOfSubarrays(self, nums: List[int], k: int): res = i = count = 0 for j,x in enumerate(nums): if x & 1: k -= 1 count = 0 while k == 0: k += nums[i] & 1 i += 1 count += 1 res += count return res def numberOfSubarrays(self, nums: List[int], k: int): n = len(nums) prefix = [0] start = float('inf') mp = collections.defaultdict(int) mp[0] = 1 for num in nums: prefix.append(prefix[-1] + int(num % 2 == 1)) if prefix[-1] >= k: start = min(start, len(prefix)-1) mp[prefix[-1]] += 1 if start == float('inf'): return 0 res = 0 for i in range(start, len(prefix)): if prefix[i] - k in mp: res += mp[prefix[i]-k] return res -
func numberOfSubarrays(nums []int, k int) (ans int) { n := len(nums) cnt := make([]int, n+1) cnt[0] = 1 t := 0 for _, v := range nums { t += v & 1 if t >= k { ans += cnt[t-k] } cnt[t]++ } return } -
function numberOfSubarrays(nums: number[], k: number): number { const n = nums.length; const cnt = new Array(n + 1).fill(0); cnt[0] = 1; let ans = 0; let t = 0; for (const v of nums) { t += v & 1; if (t - k >= 0) { ans += cnt[t - k]; } cnt[t] += 1; } return ans; }