Count Subarrays With Fixed Bounds
HardPrompt
You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
- The minimum value in the subarray is equal to
minK. - The maximum value in the subarray is equal to
maxK.
Return the number of fixed-bound subarrays.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [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 of nums is a fixed-bound subarray. There are 10 possible subarrays.
Constraints:
2 <= nums.length <= 1051 <= nums[i], minK, maxK <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible subarray of the given array nums. For each subarray, we find its minimum and maximum elements and check if they are equal to minK and maxK respectively. While straightforward, this method is computationally expensive.
Algorithm
- Initialize a counter
countto 0. - Loop through the array with an index
ifrom 0 ton-1to fix the starting point of the subarray. - Inside this loop, initialize
currentMinto a very large value andcurrentMaxto a very small value. - Start a nested loop with an index
jfromiton-1to fix the ending point of the subarray. - In the inner loop, update
currentMinandcurrentMaxwith the values from the subarraynums[i...j]. - Check if
currentMinis equal tominKandcurrentMaxis equal tomaxK. - If both conditions are met, increment the
count. - After both loops complete, return the total
count.
Walkthrough
The brute-force method is improved by avoiding redundant calculations. Instead of re-calculating the minimum and maximum for every subarray from scratch, we can maintain the currentMin and currentMax as we extend the subarray. We use two nested loops. The outer loop sets the start index i of a subarray, and the inner loop extends the subarray by moving the end index j from i to the end of the array. For each subarray nums[i...j], we update the minimum and maximum seen so far and check if they match minK and maxK. If they do, we increment our counter.
class Solution { public long countSubarrays(int[] nums, int minK, int maxK) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { int currentMin = nums[i]; int currentMax = nums[i]; for (int j = i; j < n; j++) { currentMin = Math.min(currentMin, nums[j]); currentMax = Math.max(currentMax, nums[j]); // If the subarray's bounds are outside [minK, maxK], it can't be a solution, // and no extension of it can be a solution either. So we can break. if (currentMin < minK || currentMax > maxK) { break; } if (currentMin == minK && currentMax == maxK) { count++; } } } return count; }}Complexity
Time
O(n^2) - Due to the nested loops, where `n` is the number of elements in `nums`. For each starting element, we iterate through the rest of the array.
Space
O(1) - We only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Correct for small input sizes.
Cons
Highly inefficient for large arrays.
Will result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
An optimal O(n) solution can be achieved using a single pass and a sliding window concept. The key insight is that any element outside the [minK, maxK] range acts as a delimiter, breaking the problem into smaller, independent subproblems. We can iterate through the array, keeping track of the last seen positions of minK, maxK, and the last out-of-bounds element. For each position, we can calculate how many valid subarrays end at that position.
Algorithm
- Initialize
count = 0L, and three pointers:leftBound = -1,lastMinK = -1,lastMaxK = -1. - Iterate through the array
numswith an indexjfrom 0 ton-1. - At each element
nums[j], check if it's outside the range[minK, maxK]. If it is, updateleftBound = j, as this element cannot be in any fixed-bound subarray. - If
nums[j] == minK, updatelastMinK = j. - If
nums[j] == maxK, updatelastMaxK = j. - A subarray ending at
jis valid if its start indexisatisfiesleftBound < i <= min(lastMinK, lastMaxK). - The number of such valid start indices is
min(lastMinK, lastMaxK) - leftBound. - Add
max(0L, min(lastMinK, lastMaxK) - leftBound)to the totalcount. - After the loop finishes, return
count.
Walkthrough
This approach iterates through the array just once. We maintain three crucial indices: leftBound, lastMinK, and lastMaxK. leftBound tracks the boundary of the current valid window; any element smaller than minK or larger than maxK resets this boundary. lastMinK and lastMaxK store the most recent indices where minK and maxK were found.
For each element nums[j], we consider it as the end of potential subarrays. A subarray nums[i...j] is a fixed-bound subarray if:
- All its elements are within
[minK, maxK]. This implies its start indeximust be greater thanleftBound. - It contains
minK. This impliesimust be at or before the last seenminK, i.e.,i <= lastMinK. - It contains
maxK. This impliesi <= lastMaxK.
Combining these, a valid start index i must be in the range (leftBound, min(lastMinK, lastMaxK)]. The number of integers in this range is min(lastMinK, lastMaxK) - leftBound. We add this number to our total count for each j. If min(lastMinK, lastMaxK) is not greater than leftBound, it means we haven't found both minK and maxK within the current valid window (leftBound, j], so we add 0.
class Solution { public long countSubarrays(int[] nums, int minK, int maxK) { long count = 0; int leftBound = -1; int lastMinK = -1; int lastMaxK = -1; for (int j = 0; j < nums.length; j++) { if (nums[j] < minK || nums[j] > maxK) { leftBound = j; } if (nums[j] == minK) { lastMinK = j; } if (nums[j] == maxK) { lastMaxK = j; } // The number of valid subarrays ending at j is the number of // possible start indices i. // A valid start index i must be > leftBound and <= min(lastMinK, lastMaxK). // The number of such indices is min(lastMinK, lastMaxK) - leftBound. // We use Math.max(0, ...) to handle cases where minK or maxK haven't been // seen yet in the current window, or they are outside the valid window. count += Math.max(0L, (long)Math.min(lastMinK, lastMaxK) - leftBound); } return count; }}Complexity
Time
O(n) - We iterate through the array only once, where `n` is the number of elements in `nums`.
Space
O(1) - We only use a few variables to store indices, regardless of the input size.
Trade-offs
Pros
Extremely efficient with linear time complexity.
Uses constant extra space.
Passes all constraints for the problem.
Cons
The logic can be slightly more complex to reason about compared to the brute-force approach.
Solutions
Solution
class Solution {public long countSubarrays(int[] nums, int minK, int maxK) { long ans = 0; int j1 = -1, j2 = -1, k = -1; for (int i = 0; i < nums.length; ++i) { if (nums[i] < minK || nums[i] > maxK) { k = i; } if (nums[i] == minK) { j1 = i; } if (nums[i] == maxK) { j2 = i; } ans += Math.max(0, Math.min(j1, j2) - k); } return ans; }}class Solution {public: long long countSubarrays(vector<int> &nums, int minK, int maxK) { long long ans = 0; int j1 = -1, j2 = -1, k = -1; for (int i = 0; i < nums.size(); ++i) { if (nums[i] < minK || nums[i] > maxK) k = i; if (nums[i] == minK) j1 = i; if (nums[i] == maxK) j2 = i; ans += max(0, min(j1, j2) - k); } return ans; }};class Solution: def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: j1 = j2 = k = - 1 ans = 0 for i, v in enumerate(nums): if v < minK or v > maxK: k = i if v == minK: j1 = i if v == maxK: j2 = i ans += max(0, min(j1, j2) - k) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.