Count Subarrays With Fixed Bounds
Count subarrays whose min equals minK and max equals maxK using a sliding-window with three trackers.
Problem#
Count fixed-bound subarrays of nums: those where the minimum is exactly minK and the maximum is exactly maxK.
Examples#
nums = [1,3,5,2,7,5], minK = 1, maxK = 5→2nums = [1,1,1,1], minK = 1, maxK = 1→10
Constraints#
2 <= nums.length <= 10^5, values in[1, 10^6].
Hints#
Hint 1
minK, the last index of maxK, and the last index of a value outside [minK, maxK] (a “wall”). Approach#
For each right index i, the number of valid subarrays ending at i equals min(lastMin, lastMax) - lastBad, clamped to zero. A “bad” element forbids any subarray spanning it; the smaller of the two anchor indices determines the latest start that includes both extremes.
Solution#
class Solution {public: long long countSubarrays(vector<int>& nums, int minK, int maxK) { long long ans = 0; int lastMin = -1, lastMax = -1, lastBad = -1; for (int i = 0; i < (int)nums.size(); ++i) { int v = nums[i]; if (v < minK || v > maxK) lastBad = i; if (v == minK) lastMin = i; if (v == maxK) lastMax = i; int validStart = min(lastMin, lastMax); if (validStart > lastBad) ans += validStart - lastBad; } return ans; }};func countSubarrays(nums []int, minK int, maxK int) int64 { var ans int64 lastMin, lastMax, lastBad := -1, -1, -1 for i, v := range nums { if v < minK || v > maxK { lastBad = i } if v == minK { lastMin = i } if v == maxK { lastMax = i } validStart := lastMin if lastMax < validStart { validStart = lastMax } if validStart > lastBad { ans += int64(validStart - lastBad) } } return ans}from typing import List
class Solution: def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: ans = 0 last_min, last_max, last_bad = -1, -1, -1 for i, v in enumerate(nums): if v < minK or v > maxK: last_bad = i if v == minK: last_min = i if v == maxK: last_max = i valid_start = min(last_min, last_max) if valid_start > last_bad: ans += valid_start - last_bad return ansfunction countSubarrays(nums, minK, maxK) { let ans = 0; let lastMin = -1, lastMax = -1, lastBad = -1; for (let i = 0; i < nums.length; i++) { const v = nums[i]; if (v < minK || v > maxK) lastBad = i; if (v === minK) lastMin = i; if (v === maxK) lastMax = i; const validStart = Math.min(lastMin, lastMax); if (validStart > lastBad) ans += validStart - lastBad; } return ans;}class Solution { public long countSubarrays(int[] nums, int minK, int maxK) { long ans = 0; int lastMin = -1, lastMax = -1, lastBad = -1; for (int i = 0; i < nums.length; i++) { int v = nums[i]; if (v < minK || v > maxK) lastBad = i; if (v == minK) lastMin = i; if (v == maxK) lastMax = i; int validStart = Math.min(lastMin, lastMax); if (validStart > lastBad) ans += validStart - lastBad; } return ans; }}function countSubarrays(nums: number[], minK: number, maxK: number): number { let ans = 0; let lastMin = -1, lastMax = -1, lastBad = -1; for (let i = 0; i < nums.length; i++) { const v = nums[i]; if (v < minK || v > maxK) lastBad = i; if (v === minK) lastMin = i; if (v === maxK) lastMax = i; const validStart = Math.min(lastMin, lastMax); if (validStart > lastBad) ans += validStart - lastBad; } return ans;}Editorial#
The key invariant: a subarray [l..i] is valid iff (a) it contains at least one minK and at least one maxK, and (b) it contains no value outside [minK, maxK]. Condition (b) forces l > lastBad. Condition (a) forces l <= min(lastMin, lastMax). The count of valid l is min(lastMin, lastMax) - lastBad when positive, else zero. Each element is touched once.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#