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.
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; }}Video 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.