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.
1#include <iostream>
2#include <vector>
3
4int countFixedBoundSubarrays(const std::vector<int>& nums, int minK, int maxK) {
5 int left = -1, minPos = -1, maxPos = -1;
6 int count = 0;
7 for (int right = 0; right < nums.size(); ++right) {
8 if (nums[right] < minK || nums[right] > maxK)
9 left = right;
10 if (nums[right] == minK)
11 minPos = right;
12 if (nums[right] == maxK)
13 maxPos = right;
14 count += (minPos > left && maxPos > left) ? (std::min(minPos, maxPos) - left) : 0;
15 }
16 return count;
17}
18
19int main() {
20 std::vector<int> nums = {1, 3, 5, 2, 7, 5};
21 std::cout << countFixedBoundSubarrays(nums, 1, 5) << std::endl;
22 return 0;
23}Similar to the C solution, this C++ implementation uses a sliding window approach. It keeps track of where a subarray starts becoming invalid and computes the count of subarrays ending at each valid position where both minK and maxK are present.
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.