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.
1public class SubarrayCounter {
2 public static int countFixedBoundSubarrays(int[] nums, int minK, int maxK) {
3 int count = 0;
4 for (int i = 0; i < nums.length; i++) {
5 int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
6 for (int j = i; j < nums.length; j++) {
7 minVal = Math.min(minVal, nums[j]);
8 maxVal = Math.max(maxVal, nums[j]);
9 if (minVal == minK && maxVal == maxK) {
10 count++;
11 }
12 }
13 }
14 return count;
15 }
16
17 public static void main(String[] args) {
18 int[] nums = {1, 3, 5, 2, 7, 5};
19 System.out.println(countFixedBoundSubarrays(nums, 1, 5));
20 }
21}This Java brute force solution evaluates every possible subarray to determine if the subarray contains the desired bounds defined by minK and maxK. For each valid subarray, it increments the count.