Skip to main content
Talentd

Count Subarrays With Fixed Bounds - Solution & Explanation

HardArrayQueueSliding WindowMonotonic Queue21 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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.

In this solution, we iterate over the array with a single loop. For each element, we determine if it's part of a valid subarray by checking if both minK and maxK have been encountered after the last invalid boundary. We maintain variables to track the most recent positions of minK and maxK, and a pointer to the last invalid position. The count of valid subarrays increases by the number of such subarrays ending at each valid position.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of nums, as we iterate through the array once.
Space Complexity: O(1), as we are using a fixed amount of space.

Try this approach in the editor →

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.

This brute force implementation in C iterates over all possible subarrays of the given array and checks if each subarray has a minimum value of minK and a maximum value of maxK. For each valid subarray, it increases the count.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n2) due to the nested loops for subarray examination.
Space Complexity: O(1) as it uses a fixed number of variables.

Try this approach in the editor →

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:

  1. Maintain the index k of the most recent element that is not within the range [minK, maxK], initialized to -1. The left endpoint of the current element nums[i] must be greater than k.
  2. Maintain the most recent index j_1 where the value is minK and the most recent index j_2 where the value is maxK, both initialized to -1. The left endpoint of the current element nums[i] must be less than or equal to min(j_1, j_2).
  3. 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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with Two Pointers

Time Complexity: O(n), where n is the length of nums, as we iterate through the array once.
Space Complexity: O(1), as we are using a fixed amount of space.

Brute Force

Time Complexity: O(n2) due to the nested loops for subarray examination.
Space Complexity: O(1) as it uses a fixed number of variables.

Enumerate the Right Endpoint—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n²)O(1)Useful for understanding the problem or when the array size is small.
Sliding Window with Two PointersO(n)O(1)Best choice for large arrays. Counts valid subarrays in a single pass using positional tracking.

Video Solution

2444. Count Subarrays With Fixed Bounds | Leetcode Weekly 315 | LeetCode 2444 • Bro Coders • 11,379 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Subarrays With Fixed Bounds with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Nice Subarrays

Next

Find the Number of Subarrays Where Boundary Elements Are Maximum