Abstract / Summary

Count the number of subarrays where the smallest element is at least a given lower bound and the largest element is at most a given upper bound.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 69% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Monotonic Queue
• Queue
• Sliding Window

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the number of contiguous sub-arrays whose minimum element equals minK and whose maximum element equals maxK. It does this by scanning the input list once while maintaining a small amount of state that captures the most recent positions of the required boundary values and the start of the current valid window.

Initialization

At the start the algorithm creates a counter for the answer and sets three tracking variables to None or zero.

result = 0
low  = None
high = None
left = 0

low records the latest index where minK appears, high records the latest index where maxK appears, and left marks the first index of the current segment that contains only values within the inclusive range [minK, maxK].

Main Scan

The core of the solution is a for loop that iterates over the list with both index and value.

for right, n in enumerate(nums):

During each iteration the algorithm decides whether the current element can belong to a valid sub-array.

Handling Out-of-Range Elements

If the element falls outside the allowed interval, the current segment cannot contribute any further sub-arrays. The algorithm therefore moves the left boundary past this element and discards any previously seen positions of minK and maxK.

if not (minK <= n <= maxK):
    left = right + 1
    low  = None
    high = None
    continue

This reset ensures that subsequent calculations only consider windows that are fully contained within the allowed range.

Updating Boundary Positions

When the element is inside the allowed range, the algorithm checks whether it matches either of the required extreme values. If it does, the corresponding position variable is updated to the current index. Updating on every occurrence (including repeats) correctly expands the set of sub-arrays that satisfy the fixed-boundary condition.

if n == minK:
    low = right
if n == maxK:
    high = right

Accumulating Valid Sub-Arrays

A sub-array is valid only when both low and high have been assigned, meaning that the current window contains at least one occurrence of each extreme value. The number of new sub-arrays that end at the current index is determined by the distance from the left boundary to the earlier of the two extreme positions. Adding one accounts for the sub-array that starts exactly at left.

if low is not None and high is not None:
    result += min(low, high) - left + 1

Because min(low, high) identifies the most restrictive side, every start position from left up to that index yields a sub-array whose minimum is minK and maximum is maxK.

Edge Cases Covered

The logic gracefully handles several special situations:

• Empty input - the loop never executes and the result remains zero.
• All elements within range but missing one extreme - low or high stays None, so the accumulation block never runs, yielding zero.
• Repeated occurrences of minK or maxK - each occurrence updates the corresponding index, increasing the count of sub-arrays that can end at later positions.
• minK equal to maxK - both conditions update the same index, and the calculation still works because low and high become identical, allowing sub-arrays consisting solely of that value.
• Out-of-range values interspersed - each such value triggers a reset, ensuring that sub-arrays never cross an invalid element.

Performance Optimizations

The algorithm achieves its goal with a single forward pass, avoiding nested loops or repeated scanning of the same segment. By keeping only three integer variables (left, low, high) and a counter, it uses constant additional memory regardless of input size. The early reset on out-of-range elements prevents unnecessary work on segments that cannot contribute to the answer. The use of min(low, high) directly computes the contribution for the current position without iterating over possible start indices, turning what could be a quadratic accumulation into a constant-time update per element.

Imagine you have a long train of numbered blocks. Your goal is to find all the special pieces of the train that start and end at specific spots, where every block inside is between a smallest number and a biggest number.

The code starts by looking for these blocks one by one as they roll past. It keeps track of where it last saw the smallest number and where it last saw the biggest number. If the code sees a block that is way too big or way too small, that whole section of the train is broken. It has to stop, mark that spot as a new beginning, and start looking for the special pieces all over again.

When the code finds a block that is the perfect smallest number, it remembers exactly where that spot is. When it finds a block that is the perfect biggest number, it remembers that spot too.

Whenever it has found both a smallest and a biggest number, it knows it has a valid chunk of the train. It looks at the two spots it remembered and picks the one that happened earlier. Since it knows the beginning of the current train section, it can figure out how many different ways to group those blocks work perfectly. It adds that number to a secret scoreboard to keep track of every valid combination it discovers. It just keeps doing this until it reaches the very end of the train.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++					Python		TS
	WalkCCC		Java	C++					Python
	leetcode.ca		Java	C++			C	Go	Python	Rust	TS
	Progiez		Java	C++					Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	martianoff				Scala
	shreymehul					C#
	varunu28		Java
	wisdompeak			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
martianoff	Scala
shreymehul	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality