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.
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.