Sponsored
Sponsored
This approach utilizes the sliding window technique to efficiently count subarrays that satisfy the given condition. By maintaining a window and a count of the occurrences of the maximum element within that window, we can determine the valid subarrays as we expand and contract the window.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), only constant space is used for variables.
1function countSubarrays(nums, k) {
2 let count = 0, maxCount = 0, maxElement = -1, j = 0;
3 for (let i = 0; i < nums.length; i++) {
4 if (nums[i] > maxElement) {
5 maxElement = nums[i];
6 maxCount = 1;
7 } else if (nums[i] === maxElement) {
8 maxCount++;
9 }
10 while (maxCount >= k) {
11 count += nums.length - i;
12 if (nums[j] === maxElement) {
13 maxCount--;
14 }
15 j++;
16 }
17 }
18 return count;
19}
20
21let nums = [1, 3, 2, 3, 3];
22let k = 2;
23console.log(countSubarrays(nums, k)); // Output: 6In this JavaScript implementation, the strategy is to move a window across the nums array while checking and counting subarray possibilities each time the maximum element appears at least k times.
This strategy involves iterating through the array with two pointers, resetting conditions when new maximum elements are encountered and calculating valid subarrays based on maximum occurrence counts.
Time Complexity: O(n), as we process each element in nums.
Space Complexity: O(1), no extra space besides pointer variables.
#include <iostream>
using namespace std;
int countSubarrays(vector<int>& nums, int k) {
int count = 0, left = 0, maxElement = 0, maxCount = 0;
for (int right = 0; right < nums.size(); right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.size() - right;
if (nums[left++] == maxElement) {
maxCount--;
}
}
}
return count;
}
int main() {
vector<int> nums = {1, 3, 2, 3, 3};
int k = 2;
cout << countSubarrays(nums, k) << endl; // Output: 6
return 0;
}The C++ solution manages subarray validation using a similar two-pointer technique as in C, enhancing code flexibility and clarity by using the STL vector.