Count Subarrays With Fixed Bounds solution and explanation
Google
9 more videos on this problem
2444. Count Subarrays With Fixed Bounds | Leetcode Weekly 315 | LeetCode 2444Bro Coders · 15:40 · 11K views
Count Subarrays With Fixed Bounds || Sliding Window || Leeetcode-2444Aryan Mittal · 17:39 · 11K views
Count Subarrays With Fixed Bounds | Leetcode 2444Techdose · 22:44 · 3K views
Count Subarrays With Fixed Bounds - Leetcode 2444 - PythonTechError · 9:44 · 2K views
Count Subarrays With Fixed Bounds - Leetcode 2444 - PythonCheatCode Ninja · 7:41 · 2K views
2444. Count Subarrays With Fixed Bounds (Leetcode Hard)Programming Live with Larry · 41:57 · 884 views
Let's Solve LeetCode 2444: Count Subarrays with Fixed BoundsAlex does LeetCode · 12:10 · 732 views
2444. Count Subarrays With Fixed Bounds | Leetcode Daily - PythonLeetcode Daily · 10:34 · 315 views
Count Subarrays with Fixed Bounds - Leetcode 2444 - Hard ProblemLit Code · 6:09 · 296 views
Count Subarrays With Fixed Bounds - Leetcode 2444 - PythonTim Huang · 4:31 · 144 views
The problem
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
Approach overview
Problem Overview: You are given an integer array nums and two values minK and maxK. Count how many subarrays have a minimum value equal to minK and a maximum value equal to maxK. Any subarray containing a number outside the range [minK, maxK] becomes invalid.
Approach 1: Brute Force (O(n²) time, O(1) space)
Enumerate every possible subarray starting at index i. Expand the right boundary j and track the current minimum and maximum while iterating. Each time the running minimum equals minK and the running maximum equals maxK, increment the count. This approach relies only on simple iteration over the array and constant tracking variables. It works for small inputs but becomes slow because every pair of indices is examined.
Approach 2: Sliding Window with Two Pointers (O(n) time, O(1) space)
The optimal solution scans the array once while maintaining three indices: the last position where minK appeared, the last position where maxK appeared, and the most recent index containing an invalid value (outside [minK, maxK]). While iterating, update these markers and compute how many valid subarrays end at the current position. The number of new valid subarrays equals max(0, min(lastMin, lastMax) - lastInvalid). This works because the earliest boundary that keeps both required values determines the valid starting range. The technique is a classic sliding window pattern that avoids recomputing minimum and maximum repeatedly.
Although the problem is tagged with queue and monotonic queue, you do not need those structures here. The key insight is positional tracking rather than maintaining a dynamic min/max structure.
Recommended for interviews: The sliding window solution is what interviewers expect. It demonstrates strong reasoning about window boundaries and counting subarrays in linear time. Brute force shows baseline understanding of the constraints, but the O(n) approach proves you can optimize using pointer tracking and window invariants.
Approach 1: Sliding Window with Two Pointers
This approach uses a sliding window technique with two pointers to efficiently count the subarrays. As we iterate through the array, we maintain a range that tracks the valid subarrays containing both minK and maxK. When a valid subarray is found, we slide the window to find other subarrays that meet the criteria.
def count_fixed_bound_subarrays(nums, minK, maxK):
left = min_pos = max_pos = -1
count = 0
for right, num in enumerate(nums):
if num < minK or num > maxK:
left = right
if num == minK:
min_pos = right
if num == maxK:
max_pos = right
if min_pos > left and max_pos > left:
count += min(min_pos, max_pos) - left
return count
# Example usage:
print(count_fixed_bound_subarrays([1, 3, 5, 2, 7, 5], 1, 5))public class SubarrayCounter {
public static int countFixedBoundSubarrays(int[] nums, int minK, int maxK) {
int left = -1, minPos = -1, maxPos = -1;
int count = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] < minK || nums[right] > maxK)
left = right;
if (nums[right] == minK)
minPos = right;
if (nums[right] == maxK)
maxPos = right;
if (minPos > left && maxPos > left) {
count += Math.min(minPos, maxPos) - left;
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 2, 7, 5};
System.out.println(countFixedBoundSubarrays(nums, 1, 5));
}
}#include <iostream>
#include <vector>
int countFixedBoundSubarrays(const std::vector<int>& nums, int minK, int maxK) {
int left = -1, minPos = -1, maxPos = -1;
int count = 0;
for (int right = 0; right < nums.size(); ++right) {
if (nums[right] < minK || nums[right] > maxK)
left = right;
if (nums[right] == minK)
minPos = right;
if (nums[right] == maxK)
maxPos = right;
count += (minPos > left && maxPos > left) ? (std::min(minPos, maxPos) - left) : 0;
}
return count;
}
int main() {
std::vector<int> nums = {1, 3, 5, 2, 7, 5};
std::cout << countFixedBoundSubarrays(nums, 1, 5) << std::endl;
return 0;
}function countFixedBoundSubarrays(nums, minK, maxK) {
let left = -1, minPos = -1, maxPos = -1;
let count = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] < minK || nums[right] > maxK)
left = right;
if (nums[right] === minK)
minPos = right;
if (nums[right] === maxK)
maxPos = right;
if (minPos > left && maxPos > left) {
count += Math.min(minPos, maxPos) - left;
}
}
return count;
}
// Example usage:
console.log(countFixedBoundSubarrays([1, 3, 5, 2, 7, 5], 1, 5));#include <stdio.h>
int countFixedBoundSubarrays(int* nums, int numsSize, int minK, int maxK) {
int left = -1, minPos = -1, maxPos = -1;
int count = 0;
for (int right = 0; right < numsSize; ++right) {
if (nums[right] < minK || nums[right] > maxK)
left = right;
if (nums[right] == minK)
minPos = right;
if (nums[right] == maxK)
maxPos = right;
count += (minPos > left && maxPos > left) ? (left + 1) : 0;
}
return count;
}
int main() {
int nums[] = {1, 3, 5, 2, 7, 5};
int result = countFixedBoundSubarrays(nums, 6, 1, 5);
printf("%d\n", result);
return 0;
}using System;
public class SubarrayCounter {
public static int CountFixedBoundSubarrays(int[] nums, int minK, int maxK) {
int left = -1, minPos = -1, maxPos = -1;
int count = 0;
for (int right = 0; right < nums.Length; right++) {
if (nums[right] < minK || nums[right] > maxK)
left = right;
if (nums[right] == minK)
minPos = right;
if (nums[right] == maxK)
maxPos = right;
if (minPos > left && maxPos > left) {
count += Math.Min(minPos, maxPos) - left;
}
}
return count;
}
public static void Main(string[] args) {
int[] nums = { 1, 3, 5, 2, 7, 5 };
Console.WriteLine(CountFixedBoundSubarrays(nums, 1, 5));
}
}The Python solution iterates through the array while maintaining indices for the last valid position of both minK and maxK. It adjusts the start of the subarray when encountering a number outside the boundaries and counts valid subarrays suitably.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Brute Force
This approach uses a brute force method to count fixed-bound subarrays by examining all possible subarrays in the provided array. For each subarray, check if the minimum and maximum elements match minK and maxK respectively.
def count_fixed_bound_subarrays(nums, minK, maxK):
count = 0
for i in range(len(nums)):
min_val, max_val = float('inf'), float('-inf')
for j in range(i, len(nums)):
min_val = min(min_val, nums[j])
max_val = max(max_val, nums[j])
if min_val == minK and max_val == maxK:
count += 1
return count
# Example usage:
print(count_fixed_bound_subarrays([1, 3, 5, 2, 7, 5], 1, 5))public class SubarrayCounter {
public static int countFixedBoundSubarrays(int[] nums, int minK, int maxK) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
for (int j = i; j < nums.length; j++) {
minVal = Math.min(minVal, nums[j]);
maxVal = Math.max(maxVal, nums[j]);
if (minVal == minK && maxVal == maxK) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 2, 7, 5};
System.out.println(countFixedBoundSubarrays(nums, 1, 5));
}
}#include <iostream>
#include <vector>
#include <climits>
int countFixedBoundSubarrays(const std::vector<int>& nums, int minK, int maxK) {
int count = 0;
for (int i = 0; i < nums.size(); ++i) {
int minVal = INT_MAX, maxVal = INT_MIN;
for (int j = i; j < nums.size(); ++j) {
minVal = std::min(minVal, nums[j]);
maxVal = std::max(maxVal, nums[j]);
if (minVal == minK && maxVal == maxK) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 3, 5, 2, 7, 5};
std::cout << countFixedBoundSubarrays(nums, 1, 5) << std::endl;
return 0;
}function countFixedBoundSubarrays(nums, minK, maxK) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let minVal = Infinity, maxVal = -Infinity;
for (let j = i; j < nums.length; j++) {
minVal = Math.min(minVal, nums[j]);
maxVal = Math.max(maxVal, nums[j]);
if (minVal === minK && maxVal === maxK) {
count++;
}
}
}
return count;
}
// Example usage:
console.log(countFixedBoundSubarrays([1, 3, 5, 2, 7, 5], 1, 5));#include <stdio.h>
#include <limits.h>
int countFixedBoundSubarrays(int* nums, int numsSize, int minK, int maxK) {
int count = 0;
for (int i = 0; i < numsSize; ++i) {
int min = INT_MAX, max = INT_MIN;
for (int j = i; j < numsSize; ++j) {
if (nums[j] < min) min = nums[j];
if (nums[j] > max) max = nums[j];
if (min == minK && max == maxK) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 3, 5, 2, 7, 5};
int result = countFixedBoundSubarrays(nums, 6, 1, 5);
printf("%d\n", result);
return 0;
}using System;
public class SubarrayCounter {
public static int CountFixedBoundSubarrays(int[] nums, int minK, int maxK) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
int minVal = int.MaxValue, maxVal = int.MinValue;
for (int j = i; j < nums.Length; j++) {
minVal = Math.Min(minVal, nums[j]);
maxVal = Math.Max(maxVal, nums[j]);
if (minVal == minK && maxVal == maxK) {
count++;
}
}
}
return count;
}
public static void Main(string[] args) {
int[] nums = { 1, 3, 5, 2, 7, 5 };
Console.WriteLine(CountFixedBoundSubarrays(nums, 1, 5));
}
}In this exploratory Python solution, we go through each starting index in the array and check subsequences to identify those whose minimum and maximum values match the constraints of minK and maxK.
Time Complexity: O(n2)
Space Complexity: O(1)
Approach 3: Enumerate the Right Endpoint
According to the problem description, we know that all elements of a bounded subarray are within the range [minK, maxK], and the minimum value must be minK, while the maximum value must be maxK.
We iterate through the array nums and count the number of bounded subarrays with nums[i] as the right endpoint. Then, we sum up all the counts.
The specific implementation logic is as follows:
- Maintain the index
kof the most recent element that is not within the range[minK, maxK], initialized to-1. The left endpoint of the current elementnums[i]must be greater thank. - Maintain the most recent index
j_1where the value isminKand the most recent indexj_2where the value ismaxK, both initialized to-1. The left endpoint of the current elementnums[i]must be less than or equal tomin(j_1, j_2). - Based on the above, the number of bounded subarrays with the current element as the right endpoint is
max\bigl(0,\ min(j_1, j_2) - k\bigr). Accumulate all these counts to get the result.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function countSubarrays(nums: number[], minK: number, maxK: number): number {
let ans = 0;
let [j1, j2, k] = [-1, -1, -1];
for (let 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;
}func countSubarrays(nums []int, minK int, maxK int) int64 {
ans := 0
j1, j2, k := -1, -1, -1
for i, v := range nums {
if v < minK || v > maxK {
k = i
}
if v == minK {
j1 = i
}
if v == maxK {
j2 = i
}
ans += max(0, min(j1, j2)-k)
}
return int64(ans)
}impl Solution {
pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
let mut ans: i64 = 0;
let mut j1: i64 = -1;
let mut j2: i64 = -1;
let mut k: i64 = -1;
for (i, &v) in nums.iter().enumerate() {
let i = i as i64;
if v < min_k || v > max_k {
k = i;
}
if v == min_k {
j1 = i;
}
if v == max_k {
j2 = i;
}
let m = j1.min(j2);
if m > k {
ans += m - k;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Two Pointers | Time Complexity: O(n) |
| Brute Force | Time Complexity: O(n2) |
| Enumerate the Right Endpoint | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Useful for understanding the problem or when the array size is small. |
| Sliding Window with Two Pointers | O(n) | O(1) | Best choice for large arrays. Counts valid subarrays in a single pass using positional tracking. |
Frequently asked questions
Is Count Subarrays With Fixed Bounds easy or hard?
LeetCode classifies this problem as Hard because the counting logic is subtle. The difficulty comes from realizing that valid subarrays can be counted using the positions of minK, maxK, and the last invalid element rather than explicitly enumerating all windows.
Count Subarrays With Fixed Bounds Python/Java solution
The sliding window logic translates directly across languages. Maintain three indices (lastMin, lastMax, lastInvalid) while scanning the array and update the result using the formula min(lastMin, lastMax) - lastInvalid. This O(n) approach works efficiently in Python, Java, C++, C#, and JavaScript.
How to solve Count Subarrays With Fixed Bounds in O(n)?
Iterate through the array while tracking three indices: lastMin (last index of minK), lastMax (last index of maxK), and lastInvalid (last index where value is outside the allowed range). For each position i, compute valid subarrays ending at i using max(0, min(lastMin, lastMax) - lastInvalid). This counts all starts that keep both bounds inside the window.
What is the best approach for Count Subarrays With Fixed Bounds?
The optimal approach uses a sliding window with positional tracking. While iterating through the array, keep the last index of minK, the last index of maxK, and the last invalid index where the value falls outside [minK, maxK]. At each step, compute how many valid subarrays end at the current position. This produces an O(n) time and O(1) space solution.
Is Count Subarrays With Fixed Bounds asked at Google/Amazon/Meta?
This pattern appears frequently in interviews at companies like Amazon, Google, and Meta because it tests sliding window reasoning and subarray counting techniques. Interviewers expect candidates to move from a brute force idea to an O(n) window-based solution.
What data structure is used in Count Subarrays With Fixed Bounds?
The optimal solution primarily uses the sliding window technique with index tracking. No complex data structure is required—just a few integer variables to record positions of minK, maxK, and invalid elements. The problem is sometimes tagged with monotonic queue concepts but they are not necessary here.
What is the time complexity of Count Subarrays With Fixed Bounds?
The optimal sliding window solution runs in O(n) time because each element is processed once while updating index markers. The brute force approach checks all subarrays and runs in O(n²) time. Both methods use O(1) extra space.