Count Subarrays With Fixed Bounds — Problem & Solution
Count Subarrays With Fixed Bounds solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Subarrays With Fixed Bounds is a hard coding problem on arrays, two pointers and sliding window, asked in Amazon, Google, Flipkart and Morgan Stanley interviews.
- Difficulty: Hard
- Topics: Arrays, Two Pointers, Sliding Window, Queue
- Asked at: Amazon, Google, Flipkart, Morgan Stanley, MathWorks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subarray is fixed-bound when its minimum is exactly minK and its maximum is exactly maxK.
Return the number of fixed-bound subarrays of nums.
Example 1
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: [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 qualifies.
Example 3
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 9
Output: 0
Explanation: No element equals 9.
Constraints
2 <= nums.length <= 500001 <= nums[i], minK, maxK <= 1000000
Hints for Count Subarrays With Fixed Bounds
Hint 1
A valid subarray must contain at least one
minK, at least onemaxK, and nothing outside[minK, maxK].Hint 2
Fix the right end and track three positions: the last
minK, the lastmaxK, and the last out-of-range element.Hint 3
The valid left ends sit strictly after the out-of-range element and at or before both of the other two.
How to solve Count Subarrays With Fixed Bounds
For each right end, the set of valid left ends is an interval determined by three running positions. Counting its size at every step totals every valid subarray in one pass.
Approach
- Track
lastBad(the most recent element outside[minK, maxK]),lastMinandlastMax. - At index
i, update whichever of the three applies. - The valid starts are
lastBad + 1 … min(lastMin, lastMax); addmin(lastMin, lastMax) - lastBadwhen positive.
Why it works
A subarray [l, i] is fixed-bound exactly when it avoids every out-of-range element (l > lastBad) and still reaches back to an occurrence of each bound (l <= lastMin and l <= lastMax). Those constraints define a contiguous range of l, whose size is the expression above — and it is 0 or negative precisely when no valid start exists.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Using
>=instead of>againstlastBadadmits the out-of-range element itself. minKmay equalmaxK, in which case both positions track the same index.- The count reaches about
1.25 · 10^9at the stated size — accumulate carefully.
Reference solution
Python
from typing import List
def countSubarraysFixedBounds(nums: List[int], minK: int, maxK: int) -> int:
res = 0
last_min = last_max = last_bad = -1
for i, x in enumerate(nums):
if x < minK or x > maxK:
last_bad = i
if x == minK:
last_min = i
if x == maxK:
last_max = i
lo = min(last_min, last_max)
if lo > last_bad:
res += lo - last_bad
return resJava
public static int countSubarraysFixedBounds(int[] nums, int minK, int maxK) {
long res = 0;
int lastMin = -1, lastMax = -1, lastBad = -1;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (x < minK || x > maxK) lastBad = i;
if (x == minK) lastMin = i;
if (x == maxK) lastMax = i;
int lo = Math.min(lastMin, lastMax);
if (lo > lastBad) res += lo - lastBad;
}
return (int) res;
}C++
int countSubarraysFixedBounds(vector<int>& nums, int minK, int maxK) {
long long res = 0;
int lastMin = -1, lastMax = -1, lastBad = -1;
for (int i = 0; i < (int) nums.size(); i++) {
int x = nums[i];
if (x < minK || x > maxK) lastBad = i;
if (x == minK) lastMin = i;
if (x == maxK) lastMax = i;
int lo = min(lastMin, lastMax);
if (lo > lastBad) res += lo - lastBad;
}
return (int) res;
}JavaScript
var countSubarraysFixedBounds = function(nums, minK, maxK) {
var res = 0, lastMin = -1, lastMax = -1, lastBad = -1;
for (var i = 0; i < nums.length; i++) {
var x = nums[i];
if (x < minK || x > maxK) lastBad = i;
if (x === minK) lastMin = i;
if (x === maxK) lastMax = i;
var lo = Math.min(lastMin, lastMax);
if (lo > lastBad) res += lo - lastBad;
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique