Count Subarrays With Fixed Bounds
Asked at Adobe
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.
Asked At
| 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).
Visual walkthrough for 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 (in bounds). last_minK=0, last_maxK=-1. add max(0, -1-(-1)) = 0.
i=2: num=5(maxK). last_maxK=2. add max(0, 0-(-1)) = 1. Subarray [1,3,5].
i=3: num=2. last_minK=0, last_maxK=2. add max(0, 0-(-1)) = 1. Subarray [1,3,5,2].
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.
Total: 0+0+1+1+0+0 = 2.
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.