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.
1#include <stdio.h>
2
3int countSubarrays(int* nums, int numsSize, int k) {
4 int count = 0, max_count = 0, max_element = -1, j = 0;
5
6 for (int i = 0; i < numsSize; i++) {
7 if (nums[i] > max_element) {
8 max_element = nums[i];
9 max_count = 1;
10 } else if (nums[i] == max_element) {
11 max_count++;
12 }
13
14 while (max_count >= k) {
15 count += numsSize - i;
16 if (nums[j] == max_element) {
17 max_count--;
18 }
19 j++;
20 }
21 }
22
23 return count;
24}
25
26int main() {
27 int nums[] = {1, 3, 2, 3, 3};
28 int k = 2;
29 printf("%d\n", countSubarrays(nums, 5, k)); // Output: 6
30 return 0;
31}The code initializes a sliding window by setting pointers i and j. As we iterate through the array, we update the current maximum element and its count within the window. When the count of the maximum element reaches k or more, we add subarrays from the start of the window to the end of the array that satisfy the condition.
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.
1#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.