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.
This Python function maintains a two-point tracking mechanism for efficiently checking valid subsequences while managing dynamic changes in maximum element count.