Abstract / Summary

Given a list of scores and a number k, find the smallest difference between the highest and lowest scores when choosing k scores.

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 66% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Sliding Window
• Sorting

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 solves the problem of finding the smallest possible difference between the maximum and minimum values of any contiguous sub-array of length k after the input list nums is reordered. The algorithm follows a classic “sort-then-slide” approach: it first orders the elements, then examines every window of size k in the sorted sequence, keeping track of the minimal range encountered. The final result is the minimal difference across all such windows.

Key Steps

Initialization

The variable that will hold the best answer is created with a value that is larger than any feasible difference.

result = +inf

Using positive infinity guarantees that the first computed range will replace the initial placeholder, regardless of the actual numbers in the input.

Sorting the Input

Before any window can be examined, the list is sorted in non-decreasing order.

nums.sort()

Sorting transforms the problem into a linear scan because, in a sorted array, the difference between the largest and smallest elements of any k-element subset is simply the difference between the elements at the two ends of the corresponding window.

Sliding Window Scan

The core of the algorithm iterates from the index that marks the end of the first possible window (k-1) up to the last index of the sorted list. For each position i, the start of the window is i-k+1. The two boundary values are extracted, their difference computed, and the global minimum updated.

for i in range(k - 1, len(nums)):
    one = nums[i - k + 1]
    two = nums[i]
    result = min(result, two - one)

The loop runs exactly once for each possible window, and the use of direct indexing (nums[i] and nums[i - k + 1]) avoids the overhead of creating sub-lists or additional data structures.

Returning the Answer

After all windows have been examined, the smallest observed difference is returned.

return result

Because result was initialized to infinity and updated on every iteration, it always holds a valid numeric answer when the function exits.

Edge Cases Handled

When the requested window size k equals the length of nums, the loop executes a single iteration. The algorithm correctly computes the difference between the overall maximum and minimum of the entire list, which is the only possible range.

If k is 1, each window consists of a single element. The difference two - one becomes zero for every iteration, and the minimum of zero and infinity yields zero. Consequently, the function returns zero, reflecting that a single element has no spread.

The initial sorting step also implicitly handles inputs that are already sorted, unsorted, or contain duplicate values. Duplicate entries produce a zero difference when they appear together in a window, and the algorithm captures that scenario without special-case logic.

Performance Optimizations

The design leverages the fact that sorting once enables a linear-time scan to evaluate all candidate windows. By avoiding nested loops or repeated sorting, the overall work scales with the size of the input rather than with the combinatorial number of possible subsets.

Inside the loop, the algorithm stores the two boundary values in local variables (one and two). This practice reduces the number of attribute lookups on the list object, which can be noticeable in tight loops.

The use of the built-in min function to update result is efficient because it is implemented in C and operates on primitive numeric types without additional Python-level overhead.

Finally, the function does not allocate any auxiliary containers during the scan; it works directly on the sorted list, keeping the memory footprint minimal.

Imagine you have a big messy pile of numbered blocks. Some have small numbers and some have huge numbers. This code works like a fun game to find the smallest gap between a group of blocks.

First, the code lines up all the blocks in order from the smallest number to the largest number, just like putting your toys in a nice straight row. Once they are all lined up, it looks at a small chunk of blocks that is exactly the size you requested. It checks the very first block and the very last block in that chunk to see how far apart their numbers are. If the gap is smaller than the smallest gap found so far, it remembers that one instead. It keeps sliding that chunk along the line until it reaches the very end of the row of blocks, always keeping track of the shortest distance it finds. It essentially scans through the line over and over until it knows exactly which tiny gap is the absolute smallest of them all.

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++		Java		Python					TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python	Go		PHP	Rust	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	lkwq007					Python
	suxrobGM							C#
	varunu28			Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, PHP, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
withaarzoo	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