Count Subarrays With Fixed Bounds [Hard] — One-Pass Window
Sanjeev SharmaAdvertisement
Problem Statement
Count subarrays where the minimum value equals minK and maximum equals maxK.
Input: nums=[1,3,5,2,7,5], minK=1, maxK=5 → Output: 2
Intuition
Track:
bad: last index wherenums[i] < minK or nums[i] > maxK(breaks window)min_pos: last index wherenums[i] == minKmax_pos: last index wherenums[i] == maxK
For each i, valid starting positions = max(0, min(min_pos, max_pos) - bad).
Solutions
C++
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
long long ans=0;
int bad=-1, minPos=-1, maxPos=-1;
for(int i=0;i<nums.size();i++){
if(nums[i]<minK||nums[i]>maxK) bad=i;
if(nums[i]==minK) minPos=i;
if(nums[i]==maxK) maxPos=i;
ans+=max(0,min(minPos,maxPos)-bad);
}
return ans;
}
Python
def countSubarrays(nums: list[int], minK: int, maxK: int) -> int:
ans = 0
bad = min_pos = max_pos = -1
for i, v in enumerate(nums):
if v < minK or v > maxK: bad = i
if v == minK: min_pos = i
if v == maxK: max_pos = i
ans += max(0, min(min_pos, max_pos) - bad)
return ans
Complexity
- Time: O(n), Space: O(1)
Advertisement
