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.
public class Solution {
public int CountSubarrays(int[] nums, int k) {
int count = 0, left = 0, maxElement = 0, maxCount = 0;
for (int right = 0; right < nums.Length; right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.Length - right;
if (nums[left++] == maxElement) {
maxCount--;
}
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 3, 2, 3, 3};
int k = 2;
Console.WriteLine(sol.CountSubarrays(nums, k)); // Output: 6
}
}The C# algorithm operates by controlling the sequence using dynamics between the two-pointer configuration and the maximum value encountered, ensuring it’s logged correctly through controlled increments.