Watch 10 video solutions for Count Subarrays With Fixed Bounds, a hard level problem involving Array, Queue, Sliding Window. This walkthrough by codestorywithMIK has 29,230 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |