Abstract / Summary

Find the longest part of a number list where the biggest and smallest numbers differ by no more than a given limit.

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 58% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Heap (Priority Queue)
• Monotonic Queue
• Ordered Set
• 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 implementation computes the length of the longest contiguous sub-array whose elements differ by no more than a given limit. It employs a sliding-window technique combined with two priority queues (heaps) to maintain the current window’s minimum and maximum values efficiently. The algorithm expands the window by iterating through the input list and contracts it only when the absolute difference between the current extremes exceeds limit. The maximum window size observed during the scan is returned.

Core Logic

The method begins by establishing the variables that drive the sliding window.

result = 0
low   = []
high  = []
start = 0

result stores the best length found so far. low and high are min-heaps that will hold pairs of (value, index). low keeps the actual values to expose the minimum, while high stores the negated values so that the smallest element of the heap corresponds to the maximum of the window. start marks the left boundary of the current window.

The main loop enumerates the input array, pushing each element into both heaps.

for i, n in enumerate(nums):
    heappush(high, (-n, i))   # max-heap via negation
    heappush(low,  ( n, i))   # min-heap

At this point the heaps contain all elements of the window [start, i]. The algorithm then checks whether the window violates the limit.

while -high[0][0] - low[0][0] > limit:
    if high[0][1] > low[0][1]:
        start = max(start, 1 + heappop(low)[1])
    else:
        start = max(start, 1 + heappop(high)[1])

The condition -high[0][0] - low[0][0] > limit compares the current maximum (retrieved from high) with the current minimum (retrieved from low). If the difference is too large, the window must be shrunk. The inner logic removes the older of the two extreme elements: the element whose index is smaller is the one that leaves the window first. By popping from the appropriate heap and advancing start past the removed element’s index, the window contracts just enough to restore validity.

After any necessary contraction, the length of the valid window is computed and the global maximum is updated.

length = i - start + 1
result = max(result, length)

When the loop finishes, result holds the length of the longest sub-array satisfying the constraint, and it is returned.

Edge Cases Handled

When the input list is empty, the loop body never executes, leaving result at its initial value of 0, which correctly represents the absence of any sub-array.

If the list contains a single element, the heaps receive that element, the while-condition evaluates to false because the difference between max and min is zero, and the computed length becomes 1. The method therefore returns 1, the correct answer for a solitary element regardless of the limit.

A limit of zero forces the window to contain only equal values. The while-loop removes any element that introduces a difference, effectively resetting the window each time a distinct value appears. The algorithm thus returns the length of the longest run of identical numbers.

When all numbers are identical, the difference between the extremes never exceeds limit, so the while-loop never triggers. The window expands to cover the entire array, and the final result equals the array length.

For strictly increasing or decreasing sequences, the heaps always contain the newest element as the current extreme. The while-loop removes the older extreme as soon as the difference surpasses limit, ensuring that the window slides forward correctly without missing any potential longer sub-array.

Indices are stored alongside values, guaranteeing that even when duplicate values exist, the algorithm can distinguish which occurrence should be discarded when the window contracts. This prevents accidental removal of a later occurrence that still belongs to the current window.

Performance Optimizations

The dual-heap arrangement provides constant-time access to both the minimum and maximum of the current window, while insertion and removal operations run in logarithmic time relative to the window size. By storing the original index with each heap entry, the code avoids the need for explicit element deletion from the opposite heap; instead, it lazily discards stale entries when they surface at the top of a heap.

The start pointer advances only forward, and each element is popped from a heap at most once. Consequently, the total number of heap operations across the entire execution is bounded by twice the number of input elements, keeping the overall work linear in the size of the input.

The use of max(start, 1 + popped_index) ensures that start never moves backward, preserving the monotonic progression of the sliding window and preventing unnecessary recomputation of window boundaries.

By updating result only after the window has been validated, the algorithm avoids redundant checks and maintains a minimal amount of state. The combination of these techniques yields an efficient solution that scales well with large input arrays.

Imagine a long train made of many colorful toy cars. Each car has a different number painted on the side. The goal is to find the longest part of this train where the difference between the biggest number and the smallest number is not too large.

Think of holding two special baskets. one basket helps find the biggest car, and the other basket helps find the smallest car. As the train moves past, new cars are added to the baskets one by one. If the difference between the biggest and smallest gets too big, that means the part of the train being checked is invalid.

When that happens, cars are taken away from the front of the train until the difference is small again. Every time a part of the train is safe, the length of that part is measured. The train keeps moving until the end is reached, and the length of the biggest safe part found is kept for the final answer.

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

Time: loglinear
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	C++	Python		Java			TS
	WalkCCC	C++
	leetcode.ca	C++	Python		Java		Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	shreymehul					C#
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
shreymehul	C#
suxrobGM	C#
trung-hn	Python
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