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.
1using System;
2
3public class SubarrayCounter {
4 public static int CountFixedBoundSubarrays(int[] nums, int minK, int maxK) {
5 int count = 0;
6 for (int i = 0; i < nums.Length; i++) {
7 int minVal = int.MaxValue, maxVal = int.MinValue;
8 for (int j = i; j < nums.Length; j++) {
9 minVal = Math.Min(minVal, nums[j]);
10 maxVal = Math.Max(maxVal, nums[j]);
11 if (minVal == minK && maxVal == maxK) {
12 count++;
13 }
14 }
15 }
16 return count;
17 }
18
19 public static void Main(string[] args) {
20 int[] nums = { 1, 3, 5, 2, 7, 5 };
21 Console.WriteLine(CountFixedBoundSubarrays(nums, 1, 5));
22 }
23}This C# implementation performs a brute force check, examining each potential subarray for its bounds. The solution is simple but relatively inefficient due to the extensive number of checks it performs.