#2444

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count Subarrays With Fixed Bounds

Count all subarrays where the minimum and maximum match given bounds using efficient sliding window tracking techniques.

array queue sliding window monotonic queue

Problem Statement

Given an integer array nums and two integers minK and maxK, count all subarrays where the smallest element equals minK and the largest equals maxK. Only contiguous subarrays that satisfy these bounds are valid.

Return the total number of fixed-bound subarrays. Each subarray must include at least one minK and one maxK, and all elements must stay within minK and maxK. Examples: for nums = [1,3,5,2,7,5] with minK = 1 and maxK = 5, the valid subarrays are [1,3,5] and [1,3,5,2].

Examples

Example 1

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5

Output: 2

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

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

Solution Approach

Sliding Window with Last Seen Indices

Track the last indices of minK, maxK, and the last element outside bounds. For each position, calculate how many subarrays end at the current index using the minimum distance to the last invalid or bound index.

Incremental Count Update

Instead of enumerating all subarrays, incrementally add counts by extending the window. Each step considers only new subarrays ending at the current element and ensures both minK and maxK are included.

Edge Case Handling

Carefully handle sequences where elements equal minK or maxK multiple times. Reset counts after encountering numbers outside the bounds to avoid counting invalid subarrays, preserving the integrity of the sliding window state.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) as each element is visited once with constant-time updates for last seen indices. Space complexity is O(1) since only a few indices are stored, independent of array size.

What Interviewers Usually Probe

Can you do this in one pass using a sliding window?
Consider how to track last positions of minK, maxK, and invalid elements efficiently.
Check edge cases where minK equals maxK or repeated numbers appear.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reset when encountering an out-of-bound element.
Incorrectly counting subarrays when minK or maxK repeats.
Assuming all subarrays with minK and maxK are valid without checking intermediate elements.

Follow-up variants

Count subarrays where elements are within a dynamic range instead of fixed bounds.
Compute sum of lengths of fixed-bound subarrays instead of count.
Handle multiple pairs of minK and maxK for a single pass solution.

FAQ

What is a fixed-bound subarray in Count Subarrays With Fixed Bounds?

A subarray where the smallest element is minK, the largest is maxK, and all elements stay within these bounds.

How does the sliding window pattern apply here?

It tracks last seen minK, maxK, and invalid indices, allowing O(n) counting of valid subarrays without full enumeration.

Can this handle repeated minK or maxK elements?

Yes, GhostInterview maintains last seen indices to correctly count subarrays even with repeated bounds.

What should I watch out for when implementing?

Reset the window after any element outside minK-maxK to avoid counting invalid subarrays.

Why is this approach better than brute force?

Brute force checks all subarrays, giving O(n^2) time; sliding window with state tracking reduces it to O(n).

terminal

Solution

Solution 1: Enumerate the Right Endpoint

According to the problem description, we know that all elements of a bounded subarray are within the range $[\textit{minK}, \textit{maxK}]$, and the minimum value must be $\textit{minK}$, while the maximum value must be $\textit{maxK}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

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 ans

Continue Practicing

#2398 maximum number of robots within budget #2762 continuous subarrays #1499 max value of equation