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 <iostream>
2#include <vector>
3
4int countFixedBoundSubarrays(const std::vector<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.size(); ++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 count += (minPos > left && maxPos > left) ? (std::min(minPos, maxPos) - left) : 0;
15 }
16 return count;
17}
18
19int main() {
20 std::vector<int> nums = {1, 3, 5, 2, 7, 5};
21 std::cout << countFixedBoundSubarrays(nums, 1, 5) << std::endl;
22 return 0;
23}Similar to the C solution, this C++ implementation uses a sliding window approach. It keeps track of where a subarray starts becoming invalid and computes the count of subarrays ending at each valid position where both minK and maxK are present.
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 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.