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.
1public class Solution {
2 public int countSubarrays(int[] nums, int k) {
3 int count = 0, maxCount = 0, maxElement = -1, j = 0;
4 int n = nums.length;
5 for (int i = 0; i < n; i++) {
6 if (nums[i] > maxElement) {
7 maxElement = nums[i];
8 maxCount = 1;
9 } else if (nums[i] == maxElement) {
10 maxCount++;
11 }
12 while (maxCount >= k) {
13 count += n - i;
14 if (nums[j] == maxElement) {
15 maxCount--;
16 }
17 j++;
18 }
19 }
20 return count;
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] nums = {1, 3, 2, 3, 3};
26 int k = 2;
27 System.out.println(sol.countSubarrays(nums, k)); // Output: 6
28 }
29}The Java implementation follows the same pattern: iterating through the array while maintaining the current maximum count. It dynamically adjusts the counting process using two pointers to ensure only valid subarrays are counted.
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.
The C code uses two pointers (left and right) to validate subarrays. When a maximum condition changes, the calculation restarts, which ensures only subarrays with the required maximum occurrence are considered.