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.

Description Hints 3 Solution Video 15:40

2444. Count Subarrays With Fixed Bounds

Hard69.2% acceptance9 companies

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 <= 10⁵
1 <= nums[i], minK, maxK <= 10⁶

Asked at 9 companies

Mathworks Chubb Morgan Stanley Meesho Uber Microsoft

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

Can you solve the problem if all the numbers in the array were between minK and maxK inclusive?

Hint 2

Think of the inclusion-exclusion principle.

Hint 3

Divide the array into multiple subarrays such that each number in each subarray is between minK and maxK inclusive, solve the previous problem for each subarray, and sum all the answers.

15:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution