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.
1public class SubarrayCounter {
2 public static int countFixedBoundSubarrays(int[] nums, int minK, int maxK) {
3 int left = -1, minPos = -1, maxPos = -1;
4 int count = 0;
5 for (int right = 0; right < nums.length; right++) {
6 if (nums[right] < minK || nums[right] > maxK)
7 left = right;
8 if (nums[right] == minK)
9 minPos = right;
10 if (nums[right] == maxK)
11 maxPos = right;
12 if (minPos > left && maxPos > left) {
13 count += Math.min(minPos, maxPos) - left;
14 }
15 }
16 return count;
17 }
18
19 public static void main(String[] args) {
20 int[] nums = {1, 3, 5, 2, 7, 5};
21 System.out.println(countFixedBoundSubarrays(nums, 1, 5));
22 }
23}This Java solution implements a similar sliding window technique to dynamically track the indices of minK and maxK as well as where the current valid subarray can start. Every time both bounds are valid, it counts the potential subarrays from the last invalid 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#include <iostream>
2#include <vector>
3#include <climits>
4
5int countFixedBoundSubarrays(const std::vector<int>& nums, int minK, int maxK) {
6 int count = 0;
7 for (int i = 0; i < nums.size(); ++i) {
8 int minVal = INT_MAX, maxVal = INT_MIN;
9 for (int j = i; j < nums.size(); ++j) {
10 minVal = std::min(minVal, nums[j]);
11 maxVal = std::max(maxVal, nums[j]);
12 if (minVal == minK && maxVal == maxK) {
13 count++;
14 }
15 }
16 }
17 return count;
18}
19
20int main() {
21 std::vector<int> nums = {1, 3, 5, 2, 7, 5};
22 std::cout << countFixedBoundSubarrays(nums, 1, 5) << std::endl;
23 return 0;
24}In this C++ brute force solution, we iteratively check all subarrays. For each subarray, we maintain and compare the minimum and maximum values with the required minK and maxK to ensure they are valid.