You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
minK.maxK.Return the number of fixed-bound subarrays.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5 Output: 2 Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].
Example 2:
Input: nums = [1,1,1,1], minK = 1, maxK = 1 Output: 10 Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.
Constraints:
2 <= nums.length <= 1051 <= nums[i], minK, maxK <= 106Problem Overview: You are given an integer array nums and two values minK and maxK. Count how many subarrays have a minimum value equal to minK and a maximum value equal to maxK. Any subarray containing a number outside the range [minK, maxK] becomes invalid.
Approach 1: Brute Force (O(n²) time, O(1) space)
Enumerate every possible subarray starting at index i. Expand the right boundary j and track the current minimum and maximum while iterating. Each time the running minimum equals minK and the running maximum equals maxK, increment the count. This approach relies only on simple iteration over the array and constant tracking variables. It works for small inputs but becomes slow because every pair of indices is examined.
Approach 2: Sliding Window with Two Pointers (O(n) time, O(1) space)
The optimal solution scans the array once while maintaining three indices: the last position where minK appeared, the last position where maxK appeared, and the most recent index containing an invalid value (outside [minK, maxK]). While iterating, update these markers and compute how many valid subarrays end at the current position. The number of new valid subarrays equals max(0, min(lastMin, lastMax) - lastInvalid). This works because the earliest boundary that keeps both required values determines the valid starting range. The technique is a classic sliding window pattern that avoids recomputing minimum and maximum repeatedly.
Although the problem is tagged with queue and monotonic queue, you do not need those structures here. The key insight is positional tracking rather than maintaining a dynamic min/max structure.
Recommended for interviews: The sliding window solution is what interviewers expect. It demonstrates strong reasoning about window boundaries and counting subarrays in linear time. Brute force shows baseline understanding of the constraints, but the O(n) approach proves you can optimize using pointer tracking and window invariants.
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.
In this solution, we iterate over the array with a single loop. For each element, we determine if it's part of a valid subarray by checking if both minK and maxK have been encountered after the last invalid boundary. We maintain variables to track the most recent positions of minK and maxK, and a pointer to the last invalid position. The count of valid subarrays increases by the number of such subarrays ending at each valid position.
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.
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.
This brute force implementation in C iterates over all possible subarrays of the given array and checks if each subarray has a minimum value of minK and a maximum value of maxK. For each valid subarray, it increases the count.
Time Complexity: O(n2) due to the nested loops for subarray examination.
Space Complexity: O(1) as it uses a fixed number of variables.
According to the problem description, we know that all elements of a bounded subarray are within the range [minK, maxK], and the minimum value must be minK, while the maximum value must be maxK.
We iterate through the array nums and count the number of bounded subarrays with nums[i] as the right endpoint. Then, we sum up all the counts.
The specific implementation logic is as follows:
k of the most recent element that is not within the range [minK, maxK], initialized to -1. The left endpoint of the current element nums[i] must be greater than k.j_1 where the value is minK and the most recent index j_2 where the value is maxK, both initialized to -1. The left endpoint of the current element nums[i] must be less than or equal to min(j_1, j_2).max\bigl(0,\ min(j_1, j_2) - k\bigr). Accumulate all these counts to get the result.The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sliding Window with Two Pointers | Time Complexity: O(n), where n is the length of nums, as we iterate through the array once. |
| Brute Force | Time Complexity: O(n2) due to the nested loops for subarray examination. |
| Enumerate the Right Endpoint | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Useful for understanding the problem or when the array size is small. |
| Sliding Window with Two Pointers | O(n) | O(1) | Best choice for large arrays. Counts valid subarrays in a single pass using positional tracking. |
Count Subarrays With Fixed Bounds | Made Simple | Microsoft | Leetcode 2444 | codestorywithMIK • codestorywithMIK • 29,230 views views
Watch 9 more video solutions →Practice Count Subarrays With Fixed Bounds with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor