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.
1using System;
2
3public class SubarrayCounter {
4 public static int CountFixedBoundSubarrays(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.Length; 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 if (minPos > left && maxPos > left) {
15 count += Math.Min(minPos, maxPos) - left;
16 }
17 }
18 return count;
19 }
20
21 public static void Main(string[] args) {
22 int[] nums = { 1, 3, 5, 2, 7, 5 };
23 Console.WriteLine(CountFixedBoundSubarrays(nums, 1, 5));
24 }
25}In this C# implementation, a sliding window technique is used to dynamically find and count the subarrays that contain both minK and maxK as their bounds. It adjusts to the start of the invalid section upon iterating each time through the numbers.
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.
1def count_fixed_bound_subarrays(nums, minK, maxK):
2 count = 0
3 for i in range(len(nums)):
4 min_val, max_val = float('inf'), float('-inf')
5 for j in range(i, len(nums)):
6 min_val = min(min_val, nums[j])
7 max_val = max(max_val, nums[j])
8 if min_val == minK and max_val == maxK:
9 count += 1
10 return count
11
12# Example usage:
13print(count_fixed_bound_subarrays([1, 3, 5, 2, 7, 5], 1, 5))In this exploratory Python solution, we go through each starting index in the array and check subsequences to identify those whose minimum and maximum values match the constraints of minK and maxK.