1176EasyArraySliding WindowSorting

The Tightest Choice of k Readings

Tracked in this browser only

Trains the technique from

LeetCode 1984Minimum Difference Between Highest and Lowest of K Scores

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A rack holds the readings readings. Choose exactly k of them, and let the spread of a choice be its largest reading less its smallest.

Return the smallest spread any choice of k readings can manage.

Examples

Example 1

Input: readings = [1, 5, 6, 14, 15], k = 3
Output: 5

In order the readings run 1, 5, 6, 14, 15. The three standing closest together are 1, 5 and 6, spreading 5.

Example 2

Input: readings = [5, 5, 5], k = 2
Output: 0

Every reading is the same, so any two of them spread nothing at all.

Example 3

Input: readings = [1, 100000], k = 2
Output: 99999

Both readings have to be taken, so the spread is the gap between them.

Constraints

1 <= k <= readings.length <= 1000
0 <= readings[i] <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_difference(readings: list[int], k: int) -> int:

Java

public int minimumDifference(int[] readings, int k)

The intended approach

Time O(n log n) for the ordering plus one pass.Space O(n) for the ordered copy.

Only the largest and smallest of a choice matter, so the readings in between are free. That means a tightest choice can always be taken as `k` readings standing together once the rack is put in order: given any choice, the `k` readings from its smallest upwards in order spread no more. So order the rack and slide a window of `k` readings along it, taking the difference between the window's last and first readings. The smallest of those differences is the answer, and there are only as many windows as the rack is long. A window of one reading spreads nothing, which the same formula gives without any special case.

Pythonentry point: minimum_difference

def minimum_difference(readings, k):
    order = sorted(readings)
    best = None
    for i in range(len(order) - k + 1):
        span = order[i + k - 1] - order[i]
        if best is None or span < best:
            best = span
    return best

The obvious version

Take every choice of `k` readings outright, measure each one's largest less its smallest, and keep the smallest. Costs the number of ways of choosing `k` readings from the rack.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_difference(readings, k):
    from itertools import combinations
    best = None
    for pick in combinations(readings, k):
        span = max(pick) - min(pick)
        if best is None or span < best:
            best = span
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in