This approach uses a sliding window technique with two pointers to efficiently count the subarrays. As we iterate through the array, we maintain a range that tracks the valid subarrays containing both minK and maxK. When a valid subarray is found, we slide the window to find other subarrays that meet the criteria.
Time Complexity: O(n), where n is the length of nums, as we iterate through the array once.
Space Complexity: O(1), as we are using a fixed amount of space.
1function countFixedBoundSubarrays(nums, minK, maxK) {
2 let left = -1, minPos = -1, maxPos = -1;
3 let count = 0;
4 for (let right = 0; right < nums.length; right++) {
5 if (nums[right] < minK || nums[right] > maxK)
6 left = right;
7 if (nums[right] === minK)
8 minPos = right;
9 if (nums[right] === maxK)
10 maxPos = right;
11 if (minPos > left && maxPos > left) {
12 count += Math.min(minPos, maxPos) - left;
13 }
14 }
15 return count;
16}
17
18// Example usage:
19console.log(countFixedBoundSubarrays([1, 3, 5, 2, 7, 5], 1, 5));This JavaScript function uses a two-pointer approach to identify and count subarrays that have minK and maxK as the fixed bounds. It handles the adjustment of potential subarray start indices based on boundary breaches dynamically.
This approach uses a brute force method to count fixed-bound subarrays by examining all possible subarrays in the provided array. For each subarray, check if the minimum and maximum elements match minK and maxK respectively.
Time Complexity: O(n2) due to the nested loops for subarray examination.
Space Complexity: O(1) as it uses a fixed number of variables.
1#include <stdio.h>
2#include <limits.h>
3
4int countFixedBoundSubarrays(int* nums, int numsSize, int minK, int maxK) {
5 int count = 0;
6 for (int i = 0; i < numsSize; ++i) {
7 int min = INT_MAX, max = INT_MIN;
8 for (int j = i; j < numsSize; ++j) {
9 if (nums[j] < min) min = nums[j];
10 if (nums[j] > max) max = nums[j];
11 if (min == minK && max == maxK) {
12 count++;
13 }
14 }
15 }
16 return count;
17}
18
19int main() {
20 int nums[] = {1, 3, 5, 2, 7, 5};
21 int result = countFixedBoundSubarrays(nums, 6, 1, 5);
22 printf("%d\n", result);
23 return 0;
24}This brute force implementation in C iterates over all possible subarrays of the given array and checks if each subarray has a minimum value of minK and a maximum value of maxK. For each valid subarray, it increases the count.