2444. Count Subarrays With Fixed Bounds
Asked at Adobe
Difficulty
Hard
Time
O(n)
Space
O(1)
Pattern
Array
Companies
1
Problem
You get an integer array nums and two integers minK and maxK. Count how many subarrays of nums are fixed-bound.
A subarray is a contiguous slice of the array. A subarray is fixed-bound when two things are true: the smallest value inside it equals minK, and the largest value inside it equals maxK. So every element must lie between minK and maxK, and both minK and maxK must actually appear inside the slice.
Return the number of such subarrays. Subarrays are counted by their start and end positions, so two subarrays with the same values but different positions count separately.
Which slices are fixed-bound
Constraints
- ●
2 <= nums.length <= 10^5 - ●
1 <= nums[i], minK, maxK <= 10^6
Examples
nums = [1,3,5,2,7,5], minK = 1, maxK = 52nums = [1,1,1,1], minK = 1, maxK = 110Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Adobe | Hard | View all Adobe questions → |
How to Think About It
Brute force: check every subarray. There are n*(n+1)/2 subarrays. For each, scan to verify it contains both minK and maxK and all elements are within bounds. That's O(n^2) or O(n^3) - far too slow.
Key insight: as you iterate, track the most recent positions of minK, maxK, and any out-of-bounds element. Count the valid subarrays ending at the current index using those three positions.
The counting formula: let last_bad be the most recent out-of-bounds index. A valid subarray ending at i must not include an out-of-bounds element (its start must be after last_bad) and must contain both minK and maxK (its start must be at or before min(last_minK, last_maxK)). The number of valid starts is min(last_minK, last_maxK) - last_bad, clamped to be non-negative.
Why the min and not the max: both minK and maxK must appear inside the subarray. If last_minK is 3 and last_maxK is 7, a start at index 4 includes the maxK at 7 but misses the minK at 3, so it is invalid. The later of the two occurrences - which is min(last_minK, last_maxK) - forces the latest possible left boundary.
Edge cases: minK equals maxK (every valid subarray must contain that value), no out-of-bounds elements in the entire array, minK or maxK never appears (the answer stays 0).
Optimal Approach
Track three indices as you iterate: last_minK (most recent minK), last_maxK (most recent maxK), and last_bad (most recent out-of-bounds element). For each index i:
- If
nums[i]< minK ornums[i]> maxK, setlast_bad = i. - If
nums[i]== minK, setlast_minK = i. - If
nums[i]== maxK, setlast_maxK = i. - Add
max(0, min(last_minK, last_maxK) - last_bad)to the answer.
Why this works: a valid subarray ending at i cannot include an out-of-bounds element, so its start must be after last_bad. It must also contain both minK and maxK, so its start must be at or before the later of their most recent occurrences, i.e. at or before min(last_minK, last_maxK). Every starting index in that span yields a valid subarray.
Walkthrough with nums = [1,3,5,2,7,5], minK = 1, maxK = 5:
- i=0: num=1(minK). last_minK=0, last_maxK=-1, last_bad=-1. add max(0, -1-(-1)) = 0.
- i=1: num=3. add max(0, -1-(-1)) = 0.
- i=2: num=5(maxK). last_maxK=2. add max(0, 0-(-1)) = 1.
- i=3: num=2. add max(0, 0-(-1)) = 1.
- i=4: num=7 (out of bounds). last_bad=4. add max(0, 0-4) = 0.
- i=5: num=5(maxK). last_maxK=5. add max(0, 0-4) = 0.
Answer: 2 (the subarrays [1,3,5] and [1,3,5,2]).
Time: O(n). Space: O(1).
Three indices, one pass
What Trips People Up in Real Interviews
Trying to use a sliding window that expands and contracts. This problem is not a standard sliding window - there is no monotonic expansion or contraction. Instead, use the "count valid subarrays ending at each position" technique.
Using the formula i - max(last_minK, last_maxK, last_bad). That is wrong because a start between the maxK and the minK misses one of them. The correct addition is min(last_minK, last_maxK) - last_bad (clamped to zero).
Forgetting that an out-of-bounds element completely invalidates the current window. When you see a value < minK or > maxK, update last_bad. No valid subarray can cross it, so contributions stay zero until both bounds appear again.
Overcomplicating with a monotonic queue or deque. Monotonic queues are useful for min/max window problems, but this problem only needs three position trackers and a subtraction per step.
Not clamping the per-step addition to zero. min(last_minK, last_maxK) - last_bad is negative when an out-of-bounds element is more recent than one of the bounds. Use max(0, ...) so the count never decreases.
Solution Code
O(n) timedef countSubarrays(nums, minK, maxK):
count = 0
last_minK = -1
last_maxK = -1
last_bad = -1
for i, num in enumerate(nums):
if num < minK or num > maxK:
last_bad = i
if num == minK:
last_minK = i
if num == maxK:
last_maxK = i
count += max(0, min(last_minK, last_maxK) - last_bad)
return countFrequently Asked Questions
What is the Count Subarrays With Fixed Bounds problem?
Given an integer array nums and two integers minK and maxK, return the count of subarrays whose elements are bounded by minK and maxK and contain at least one occurrence of both minK and maxK. This problem tests your ability to track multiple constraints simultaneously within a sliding window.
How do you solve Count Subarrays With Fixed Bounds?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Subarrays With Fixed Bounds?
Count Subarrays With Fixed Bounds is asked at Adobe. It is a hard difficulty problem.
What are common mistakes on Count Subarrays With Fixed Bounds?
- Trying to use a sliding window that expands and contracts. This problem is not a standard sliding window - there is no monotonic expansion or contraction. Instead, use the "count valid subarrays ending at each position" technique.
- Using the formula `i - max(last_minK, last_maxK, last_bad)`. That is wrong because a start between the maxK and the minK misses one of them. The correct addition is `min(last_minK, last_maxK) - last_bad` (clamped to zero).
- Forgetting that an out-of-bounds element completely invalidates the current window. When you see a value < minK or > maxK, update `last_bad`. No valid subarray can cross it, so contributions stay zero until both bounds appear again.
- Overcomplicating with a monotonic queue or deque. Monotonic queues are useful for min/max window problems, but this problem only needs three position trackers and a subtraction per step.
- Not clamping the per-step addition to zero. `min(last_minK, last_maxK) - last_bad` is negative when an out-of-bounds element is more recent than one of the bounds. Use `max(0, ...)` so the count never decreases.