Count Subarrays With Fixed Bounds
Hard · Sliding Window · Array · Sliding Window · Monotonic Queue
Problem
You are given an integer array nums and two integers minK and maxK. A contiguous subarray is a fixed-bound subarray when its minimum equals minK and its maximum equals maxK.
Return the number of fixed-bound subarrays.
Examples
Input: nums = [2,4,3,2,6], minK = 2, maxK = 4 Output: 4
[2,4], [2,4,3], [2,4,3,2] and [4,3,2] have minimum 2 and maximum 4. None may include the 6.
Input: nums = [1,1,1], minK = 1, maxK = 1 Output: 6
Every one of the six subarrays has minimum and maximum 1.
Input: nums = [3,3,5], minK = 2, maxK = 5 Output: 0
No value equals 2, so no subarray has minimum 2.
Constraints
- 2 <= len(nums) <= 10^5
- 1 <= nums[i], minK, maxK <= 10^6
Approaches
- Baseline: every start, running min and max — time O(n²), space O(1)
Follow-up
The answer can exceed 2^31 when the array is long (all values equal and minK == maxK gives n(n+1)/2), so Java and C++ return a 64-bit count. The same last-index sweep counts subarrays whose maximum is exactly m, or that contain two given values: see the use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
