Sponsored
Sponsored
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 <stdio.h>
2
3int countFixedBoundSubarrays(int* nums, int numsSize, int minK, int maxK) {
4 int left = -1, minPos = -1, maxPos = -1;
5 int count = 0;
6 for (int right = 0; right < numsSize; ++right) {
7 if (nums[right] < minK || nums[right] > maxK)
8 left = right;
9 if (nums[right] == minK)
10 minPos = right;
11 if (nums[right] == maxK)
12 maxPos = right;
13 count += (minPos > left && maxPos > left) ? (left + 1) : 0;
14 }
15 return count;
16}
17
18int main() {
19 int nums[] = {1, 3, 5, 2, 7, 5};
20 int result = countFixedBoundSubarrays(nums, 6, 1, 5);
21 printf("%d\n", result);
22 return 0;
23}In this solution, we iterate over the array with a single loop. For each element, we determine if it's part of a valid subarray by checking if both minK and maxK have been encountered after the last invalid boundary. We maintain variables to track the most recent positions of minK and maxK, and a pointer to the last invalid position. The count of valid subarrays increases by the number of such subarrays ending at each valid position.
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
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.