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.
1def count_subarrays(nums, k):
2 count = max_count = 0
3 max_element = -1
4 j = 0
5
6 for i in range(len(nums)):
7 if nums[i] > max_element:
8 max_element = nums[i]
9 max_count = 1
10 elif nums[i] == max_element:
11 max_count += 1
12
13 while max_count >= k:
14 count += len(nums) - i
15 if nums[j] == max_element:
16 max_count -= 1
17 j += 1
18
19 return count
20
21nums = [1, 3, 2, 3, 3]
22k = 2
23print(count_subarrays(nums, k)) # Output: 6This Python function uses a sliding window approach to efficiently determine when the current subarray meets the required condition of containing the maximum element at least k times. The two pointers (i and j) allow us to maintain and update the window as needed.
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.