Count Subarrays With Fixed Bounds
Count Subarrays With Fixed Bounds is a hard arrays & hashing problem solved with the sliding window · variable pattern.
The best approach, optimal (track last wall, last mink, last maxk), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend every start) up.
Problem
You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray is a contiguous, non-empty part of nums whose smallest element is exactly minK and whose largest element is exactly maxK. Return the number of fixed-bound subarrays.
Examples
Example 1
- Input
nums = [2, 4, 3, 2, 6], minK = 2, maxK = 4- Output
4- Why
- [2, 4], [2, 4, 3], [2, 4, 3, 2] and [4, 3, 2] qualify; nothing may include the 6.
Example 2
- Input
nums = [3, 3, 3], minK = 3, maxK = 3- Output
6- Why
- Every one of the 6 subarrays has minimum 3 and maximum 3.
Example 3
- Input
nums = [1, 5, 2], minK = 2, maxK = 5- Output
1- Why
- Only [5, 2] works; anything containing the 1 has a minimum that is too small.
Constraints
2 <= nums.length <= 10^51 <= nums[i], minK, maxK <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (extend every start) | O(n²) | O(1) |
| Optimal (track last wall, last minK, last maxK) | O(n) | O(1) |
1Brute force (extend every start)
O(n²)Each start may scan to the end of the array.O(1)A few running values.For each start index, walk right while keeping the running minimum and maximum. Count every end where min == minK and max == maxK, and stop as soon as a value falls outside [minK, maxK], since no longer subarray from this start can recover.
- For each l: mn = +inf, mx = -inf.
- For r from l: update mn and mx with nums[r]; if mn < minK or mx > maxK, break.
- If mn == minK and mx == maxK, count++.
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long count = 0;
int n = nums.length;
for (int l = 0; l < n; l++) {
int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
for (int r = l; r < n; r++) {
mn = Math.min(mn, nums[r]);
mx = Math.max(mx, nums[r]);
if (mn < minK || mx > maxK) break;
if (mn == minK && mx == maxK) count++;
}
}
return count;
}
}class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
count = 0
n = len(nums)
for l in range(n):
mn, mx = float('inf'), float('-inf')
for r in range(l, n):
mn = min(mn, nums[r])
mx = max(mx, nums[r])
if mn < minK or mx > maxK:
break
if mn == minK and mx == maxK:
count += 1
return countclass Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
long long count = 0;
int n = nums.size();
for (int l = 0; l < n; l++) {
int mn = INT_MAX, mx = INT_MIN;
for (int r = l; r < n; r++) {
mn = min(mn, nums[r]);
mx = max(mx, nums[r]);
if (mn < minK || mx > maxK) break;
if (mn == minK && mx == maxK) count++;
}
}
return count;
}
};function countSubarrays(nums, minK, maxK) {
let count = 0;
const n = nums.length;
for (let l = 0; l < n; l++) {
let mn = Infinity, mx = -Infinity;
for (let r = l; r < n; r++) {
mn = Math.min(mn, nums[r]);
mx = Math.max(mx, nums[r]);
if (mn < minK || mx > maxK) break;
if (mn === minK && mx === maxK) count++;
}
}
return count;
}2Optimal (track last wall, last minK, last maxK)
O(n)One pass with constant work per index.O(1)Three indices and the running total.Scan once and remember three positions: the last index holding a value outside [minK, maxK] (a wall), the last index equal to minK and the last index equal to maxK. A subarray ending at r qualifies exactly when its start lies after the wall and at or before both of the other two positions, which gives max(0, min(lastMin, lastMax) - wall) choices.
- wall = lastMin = lastMax = -1.
- For each r: if nums[r] is outside [minK, maxK], wall = r. If nums[r] == minK, lastMin = r. If nums[r] == maxK, lastMax = r.
- Add max(0, min(lastMin, lastMax) - wall) to the answer.
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long count = 0;
int wall = -1, lastMin = -1, lastMax = -1;
for (int r = 0; r < nums.length; r++) {
if (nums[r] < minK || nums[r] > maxK) wall = r;
if (nums[r] == minK) lastMin = r;
if (nums[r] == maxK) lastMax = r;
count += Math.max(0, Math.min(lastMin, lastMax) - wall);
}
return count;
}
}class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
count = 0
wall = last_min = last_max = -1
for r, v in enumerate(nums):
if v < minK or v > maxK:
wall = r
if v == minK:
last_min = r
if v == maxK:
last_max = r
count += max(0, min(last_min, last_max) - wall)
return countclass Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
long long count = 0;
int wall = -1, lastMin = -1, lastMax = -1;
for (int r = 0; r < (int)nums.size(); r++) {
if (nums[r] < minK || nums[r] > maxK) wall = r;
if (nums[r] == minK) lastMin = r;
if (nums[r] == maxK) lastMax = r;
count += max(0, min(lastMin, lastMax) - wall);
}
return count;
}
};function countSubarrays(nums, minK, maxK) {
let count = 0;
let wall = -1, lastMin = -1, lastMax = -1;
for (let r = 0; r < nums.length; r++) {
if (nums[r] < minK || nums[r] > maxK) wall = r;
if (nums[r] === minK) lastMin = r;
if (nums[r] === maxK) lastMax = r;
count += Math.max(0, Math.min(lastMin, lastMax) - wall);
}
return count;
}Edge cases to test
- minK == maxK: every subarray made only of that value counts
- minK > maxK: no subarray can qualify
- Out-of-range values split the array into independent pieces
- The answer can exceed 32 bits
Hints
Hint 1
A qualifying subarray cannot contain any value below minK or above maxK. Those values act as walls.
Hint 2
Fix the right end r. The subarray [l, r] qualifies when l is after the last wall and at or before both the last minK and the last maxK seen so far.
Hint 3
So for each r add max(0, min(lastMin, lastMax) - lastWall). One pass, three indices.
FAQ
What is the best time complexity for Count Subarrays With Fixed Bounds?
Optimal (track last wall, last minK, last maxK) runs in O(n) time and O(1) extra space. One pass with constant work per index.
Which pattern does Count Subarrays With Fixed Bounds use?
It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.
Is there a brute force solution for Count Subarrays With Fixed Bounds?
Yes. Brute force (extend every start) takes O(n²) time and O(1) space. For each start index, walk right while keeping the running minimum and maximum.
Which edge cases should I test for Count Subarrays With Fixed Bounds?
minK == maxK: every subarray made only of that value counts; minK maxK: no subarray can qualify; Out-of-range values split the array into independent pieces; The answer can exceed 32 bits.