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.
1def count_fixed_bound_subarrays(nums, minK, maxK):
2 left = min_pos = max_pos = -1
3 count = 0
4 for right, num in enumerate(nums):
5 if num < minK or num > maxK:
6 left = right
7 if num == minK:
8 min_pos = right
9 if num == maxK:
10 max_pos = right
11 if min_pos > left and max_pos > left:
12 count += min(min_pos, max_pos) - left
13 return count
14
15# Example usage:
16print(count_fixed_bound_subarrays([1, 3, 5, 2, 7, 5], 1, 5))The Python solution iterates through the array while maintaining indices for the last valid position of both minK and maxK. It adjusts the start of the subarray when encountering a number outside the boundaries and counts valid subarrays suitably.
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.
1function countFixedBoundSubarrays(nums, minK, maxK) {
2 let count = 0;
3 for (let i = 0; i < nums.length; i++) {
4 let minVal = Infinity, maxVal = -Infinity;
5 for (let j = i; j < nums.length; j++) {
6 minVal = Math.min(minVal, nums[j]);
7 maxVal = Math.max(maxVal, nums[j]);
8 if (minVal === minK && maxVal === maxK) {
9 count++;
10 }
11 }
12 }
13 return count;
14}
15
16// Example usage:
17console.log(countFixedBoundSubarrays([1, 3, 5, 2, 7, 5], 1, 5));This JavaScript solution utilizes a double loop to check every possible subarray, ensuring it has the desired minimum and maximum bounds. It's straightforward but computationally expensive for large arrays.