LeetCode 2444 - Count Subarrays With Fixed Bounds

LeetCode Problem 2444

Difficulty: 🔴 Hard
Topics: Array, Queue, Sliding Window, Monotonic Queue

Solution

Problem Understanding

This problem asks us to count how many contiguous subarrays satisfy two exact boundary conditions at the same time:

1. The minimum element in the subarray must be exactly minK.
2. The maximum element in the subarray must be exactly maxK.

The key detail is that these are exact matches, not inequalities. A valid subarray cannot simply have values greater than or equal to minK and less than or equal to maxK. Instead, the smallest number present must equal minK, and the largest number present must equal maxK.

We are given an integer array nums and two integers, minK and maxK. The goal is to return the total number of contiguous subarrays whose minimum and maximum values are exactly equal to these bounds.

For example, if nums = [1,3,5,2], minK = 1, and maxK = 5, then [1,3,5] is valid because its minimum is 1 and its maximum is 5. Similarly, [1,3,5,2] is valid for the same reason. However, [3,5] is invalid because its minimum is 3, not 1.

The constraints are important:

• nums.length can be as large as 10^5
• Values can be as large as 10^6

Because the input size is large, any algorithm worse than roughly O(n log n) is likely too slow. A brute force solution that examines every possible subarray would require O(n²) or worse, which becomes infeasible for 10^5 elements.

Several edge cases immediately stand out:

If minK == maxK, then every valid subarray must contain only that exact value. For example, [1,1,1,1] with minK = maxK = 1 makes every subarray valid.

If elements outside the range [minK, maxK] appear, they instantly invalidate any subarray containing them. For example, if minK = 1 and maxK = 5, then a value like 7 breaks any candidate subarray.

Another tricky case occurs when one of the required values is missing. Even if all numbers lie within bounds, no subarray can be valid unless both minK and maxK appear.

Approaches

Brute Force Approach

A straightforward idea is to generate every possible subarray and compute its minimum and maximum values.

For every starting index i, we consider every ending index j, forming the subarray nums[i:j+1]. We then compute the minimum and maximum values inside that subarray and check whether:

• min(subarray) == minK
• max(subarray) == maxK

If both conditions hold, we increment our answer.

This approach is correct because it explicitly checks every possible subarray and verifies the problem constraints exactly. However, it is extremely inefficient.

There are O(n²) subarrays in an array of length n. If we recompute minimum and maximum values for each subarray, that costs O(n) per subarray, resulting in O(n³) time complexity.

Even with optimization, where we maintain running minimum and maximum while extending subarrays, we still require O(n²) time, which is too slow for n = 10^5.

Key Insight for an Optimal Solution

The crucial observation is that we do not need to inspect every subarray individually.

Instead, we can process the array in a single pass while tracking:

• The most recent index of minK
• The most recent index of maxK
• The most recent invalid index, where the value is outside [minK, maxK]

At every position i, we ask:

How many valid subarrays end at index i?

A subarray ending at i is valid only if:

1. It contains at least one minK
2. It contains at least one maxK
3. It contains no invalid values

The earliest valid start position is constrained by the most recent invalid index. Meanwhile, the latest possible start position that guarantees both required values is determined by the earlier of the latest minK and latest maxK.

This lets us compute the number of valid subarrays ending at each position in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Enumerates all subarrays and tracks min/max
Optimal Sliding Window	O(n)	O(1)	Tracks recent positions of required and invalid values

Algorithm Walkthrough

Optimal Sliding Window Algorithm

1. Initialize three indices:

• last_min_index = -1, stores the latest occurrence of minK
• last_max_index = -1, stores the latest occurrence of maxK
• last_invalid_index = -1, stores the latest index where a value falls outside [minK, maxK]

We initialize them to -1 because initially nothing has been seen. 2. Iterate through the array from left to right.

For each index i, examine nums[i]. 3. Check whether the current value is invalid.

If nums[i] < minK or nums[i] > maxK, then this element cannot appear in any valid subarray.

Update:

last_invalid_index = i

This means any future valid subarray must start strictly after this position. 4. Update the latest occurrence of minK.

If nums[i] == minK, update:

last_min_index = i 5. Update the latest occurrence of maxK.

If nums[i] == maxK, update:

last_max_index = i 6. Determine whether a valid subarray ending at i exists.

A valid subarray ending at i must contain both required values.

The limiting position is:

min(last_min_index, last_max_index)

This tells us the earliest point where both required values are guaranteed to exist. 7. Count valid starting positions.

The start index must be greater than last_invalid_index.

Therefore:

valid_count = min(last_min_index, last_max_index) - last_invalid_index

If this value is negative, no valid subarray exists ending at i, so we add 0. 8. Add the contribution to the total answer.

Every valid starting point creates one valid subarray ending at i.

Why it works

The algorithm maintains an invariant:

At every index i, we know:

• The latest position where minK appeared
• The latest position where maxK appeared
• The latest invalid boundary

A valid subarray ending at i must begin after the invalid boundary and include both required values. The earliest position where both required values are guaranteed is the smaller of the two latest required indices.

Therefore:

min(last_min_index, last_max_index) - last_invalid_index

precisely counts how many valid starting positions exist.

Since every subarray is counted exactly once, when its ending index is processed, the algorithm is correct.

Python Solution

from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        last_min_index = -1
        last_max_index = -1
        last_invalid_index = -1

        total_subarrays = 0

        for index, value in enumerate(nums):
            if value < minK or value > maxK:
                last_invalid_index = index

            if value == minK:
                last_min_index = index

            if value == maxK:
                last_max_index = index

            valid_endings = (
                min(last_min_index, last_max_index)
                - last_invalid_index
            )

            total_subarrays += max(0, valid_endings)

        return total_subarrays

The implementation closely follows the algorithm.

We first initialize tracking indices to -1, indicating that neither boundary value nor invalid elements have been seen yet.

As we iterate through the array, each element may update one or more trackers. If the element lies outside the valid range, it resets the valid search region by updating last_invalid_index.

Whenever we encounter minK or maxK, we store their latest positions. At every index, we calculate how many valid subarrays end there.

The expression:

min(last_min_index, last_max_index)

ensures both required values exist. If one has not appeared yet, the result remains -1, naturally producing zero contribution.

Finally, we accumulate all valid endings into the total count.

Go Solution

func countSubarrays(nums []int, minK int, maxK int) int64 {
	lastMinIndex := -1
	lastMaxIndex := -1
	lastInvalidIndex := -1

	var totalSubarrays int64 = 0

	for index, value := range nums {
		if value < minK || value > maxK {
			lastInvalidIndex = index
		}

		if value == minK {
			lastMinIndex = index
		}

		if value == maxK {
			lastMaxIndex = index
		}

		validEndings := min(lastMinIndex, lastMaxIndex) - lastInvalidIndex

		if validEndings > 0 {
			totalSubarrays += int64(validEndings)
		}
	}

	return totalSubarrays
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go solution mirrors the Python implementation almost exactly.

One important difference is integer handling. The problem can produce a very large number of valid subarrays, potentially close to n * (n + 1) / 2, which exceeds the range of a 32-bit integer. Therefore, the return type is int64, and we explicitly cast contributions before accumulation.

Go also does not provide a built-in min function for integers, so we define a small helper function.

Unlike Python, Go slices are already reference types, so no special handling for arrays is required.

Worked Examples

Example 1

Input:

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

i	nums[i]	last_min	last_max	last_invalid	valid endings	total
0	1	0	-1	-1	0	0
1	3	0	-1	-1	0	0
2	5	0	2	-1	1	1
3	2	0	2	-1	1	2
4	7	0	2	4	0	2
5	5	0	5	4	0	2

At index 2, the subarray [1,3,5] becomes valid.

At index 3, [1,3,5,2] is valid.

The 7 invalidates future subarrays crossing index 4.

Final answer: 2.

Example 2

Input:

nums = [1,1,1,1]
minK = 1
maxK = 1

i	nums[i]	last_min	last_max	last_invalid	valid endings	total
0	1	0	0	-1	1	1
1	1	1	1	-1	2	3
2	1	2	2	-1	3	6
3	1	3	3	-1	4	10

Every subarray is valid.

Final answer: 10.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array exactly once
Space	O(1)	Only a few tracking variables are used

The algorithm is linear because every element is processed exactly once, and each step performs constant-time updates and arithmetic.

The space complexity is constant since no additional data structures proportional to input size are created.

Test Cases

sol = Solution()

assert sol.countSubarrays([1, 3, 5, 2, 7, 5], 1, 5) == 2
# Example case

assert sol.countSubarrays([1, 1, 1, 1], 1, 1) == 10
# Every subarray valid

assert sol.countSubarrays([2, 2, 2], 1, 5) == 0
# Missing both bounds

assert sol.countSubarrays([1, 5], 1, 5) == 1
# Smallest valid subarray

assert sol.countSubarrays([1], 1, 1) == 1
# Single element valid case

assert sol.countSubarrays([1, 2, 3], 1, 3) == 1
# Only whole array works

assert sol.countSubarrays([1, 2, 7, 1, 5], 1, 5) == 1
# Invalid element splits regions

assert sol.countSubarrays([5, 1, 5, 1], 1, 5) == 6
# Multiple overlapping valid subarrays

assert sol.countSubarrays([1, 5, 1, 5, 1], 1, 5) == 10
# Dense valid combinations

assert sol.countSubarrays([8, 8, 8], 1, 5) == 0
# All elements invalid

Test	Why
[1,3,5,2,7,5]	Official example
[1,1,1,1]	minK == maxK case
[2,2,2]	Missing required values
[1,5]	Minimum valid size
[1]	Single element boundary
[1,2,3]	Only one valid subarray
[1,2,7,1,5]	Invalid value resets window
[5,1,5,1]	Overlapping valid subarrays
[1,5,1,5,1]	Stress overlapping counting
[8,8,8]	Entire array invalid

Edge Cases

When minK == maxK

This case is easy to mishandle because the minimum and maximum requirements collapse into the same value. Every valid subarray must consist entirely of that exact number.

For example:

nums = [1,1,1]
minK = 1
maxK = 1

Every subarray becomes valid. The implementation naturally handles this because both last_min_index and last_max_index update together.

Invalid Numbers Splitting the Array

Any value outside [minK, maxK] instantly invalidates every subarray containing it.

For example:

nums = [1,5,9,1,5]

The 9 forces a reset. Valid subarrays before index 2 cannot connect with those after index 2.

The algorithm handles this using last_invalid_index, ensuring future starts occur only after the invalid position.

Missing One Required Boundary

A subarray cannot be valid unless it contains both minK and maxK.

For example:

nums = [1,2,2,2]
minK = 1
maxK = 5

Although all values are within range, 5 never appears. Therefore, no valid subarray exists.

The implementation naturally handles this because one of the tracked indices remains -1, making:

min(last_min_index, last_max_index)

negative, which contributes zero to the answer.