Abstract / Summary

Count the number of subarrays where the sum of absolute differences between neighbors is less than a given value.

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 62% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Prefix Sum
• 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 defines a method countSubarrays that computes the number of contiguous sub-arrays whose average is strictly less than a given threshold k. It does so by maintaining a sliding window over the input list nums and adjusting the window bounds so that the condition have * length < k holds for the current window. The algorithm accumulates the count of valid sub-arrays by adding the current window length each time the right end of the window moves forward.

Core Logic

The method begins by initializing a result accumulator, the size of the input, and two pointers that delimit the sliding window.

result = 0
size = len(nums)
left = 0
have = 0

The main loop iterates over the array with enumerate, exposing both the index right and the element n.

for right, n in enumerate(nums):

Inside the loop the sum of the elements inside the window, stored in have, is increased by the newly included element.

have += n

The current window length is derived from the two pointers.

length = right - left + 1

A nested while loop then shrinks the window from the left as long as the product have * length meets or exceeds the threshold k. This product is equivalent to length * average, so the condition directly enforces the average constraint without performing a division.

while have * length >= k:
    have   -= nums[left]
    left   += 1
    length -= 1

When the inner loop finishes, the window satisfies the required average condition, and every sub-array that ends at right and starts anywhere between left and right (inclusive) is valid. The number of such sub-arrays equals the current window length, which is added to the cumulative result.

result += length

Finally, after processing all elements, the method returns the total count.

return result

Edge Cases Handled

When nums is empty, size becomes zero, the for loop never executes, and the method returns the initial result value of zero, correctly indicating that no sub-arrays exist.

If k is zero or negative, the condition have * length >= k is immediately true for any non-empty window because have and length are non-negative. The inner loop therefore collapses the window to an empty state (left moves past right), leaving length at zero and contributing nothing to result. This behavior correctly yields a count of zero for any input where the average cannot be less than a non-positive threshold.

When the list contains a single element, the outer loop runs once. The inner loop either removes the element (if its value alone violates the condition) or retains it (if the condition holds). In either case, result receives either zero or one, matching the expected count of valid sub-arrays of length one.

Large integer values in nums do not cause overflow because Python integers have arbitrary precision. The multiplication have * length remains exact, ensuring the average comparison stays accurate even for very large sums.

Performance Optimizations

The algorithm employs a classic two-pointer sliding window, which guarantees that each element is added to have exactly once and removed at most once. This eliminates the need for recomputing sums for overlapping sub-arrays, reducing the work to a linear pass over the input.

By comparing have * length to k instead of computing have / length < k, the implementation avoids floating-point division entirely. Multiplication is faster and preserves integer precision, which also sidesteps rounding errors that could otherwise affect the correctness of the average check.

The inner while loop only advances the left pointer when the window violates the condition. Because left never moves backward, the total number of iterations of the inner loop across the entire execution is bounded by size. Consequently, the overall number of pointer movements is linear in the length of the input.

Storing the current window length in a local variable (length) avoids repeatedly calculating right - left + 1 inside the inner loop, saving a small amount of arithmetic per iteration.

The use of enumerate provides both the index and the element in a single pass, eliminating an extra indexing operation that would be required if the loop used a separate counter.

Overall, the design leverages incremental updates and integer arithmetic to achieve an efficient, single-pass solution that scales well with input size.

Imagine a long row of building blocks lined up on the floor. Each block has a special number painted on it. The goal is to look at how many groups of blocks sitting next to each other have a sum that stays small enough after multiplying by how many blocks are in that group.

To do this, two friends move along the line of blocks. One friend stays at the left side of a group and another friend moves along the right side, expanding the group one block at a time. Every time a new block is added, the total sum of the numbers on the blocks is calculated and then multiplied by the number of blocks in that group.

If that final number gets too big and goes over the limit, the friend on the left side moves forward to make the group smaller. This keeps happening until the group becomes small enough again. Every time the group is a size that fits the rule, all the possible groups ending at that spot are counted. By sliding this window along the whole line of blocks, the total count of all valid groups is found.

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		C++	Python	Java					TS
	WalkCCC		C++	Python	Java
	leetcode.ca		C++	Python	Java			Go	Rust	TS
	Progiez		C++	Python	Java
github	AdelDaniel					Dart
	charles-wangkai				Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	lkwq007			Python
	shreymehul						C#
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
AdelDaniel	Dart
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
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