Introduction

If you want the largest possible subset of numbers such that every chosen pair differs by more than a threshold d, the standard solution is greedy after sorting. The reason it works is that choosing the earliest feasible value leaves the most room for later choices.

Restate the Problem Precisely

Given a list of numbers and a threshold d, select as many numbers as possible so that for any two selected values x and y, the absolute difference is greater than d.

That means once you choose one value, the next chosen value must be strictly more than d away from it on the sorted line.

The Greedy Idea

Sort the numbers, then walk from left to right.

• always take the first available number
• after that, take the next number whose difference from the last chosen number is greater than d
• continue until the list ends

This is optimal for maximizing the number of selected points on a line under a minimum-spacing rule. Picking the earliest feasible number cannot reduce the number of future picks, because any later replacement would only consume the same or more space to the right.

A Python Implementation

Here is a direct implementation.

1from typing import Iterable, List
2
3
4def max_spaced_subset(values: Iterable[float], d: float) -> List[float]:
5    values = sorted(values)
6    if not values:
7        return []
8
9    selected = [values[0]]
10
11    for value in values[1:]:
12        if value - selected[-1] > d:
13            selected.append(value)
14
15    return selected
16
17
18nums = [1, 3, 4, 7, 9, 10]
19print(max_spaced_subset(nums, 1.5))

For this example, the result is [1, 3, 7, 9]. Each adjacent chosen value differs by more than 1.5, and no larger valid subset exists.

Why Sorting Is Enough

Once the values are sorted, the pairwise constraint becomes local in the greedy construction. If every newly chosen value is more than d away from the previously chosen one, it is automatically more than d away from all earlier chosen values too, because the earlier values are even farther left.

That is what keeps the algorithm simple. You do not need to compare each candidate with every selected value.

Complexity

Sorting costs O(n log n), which dominates the runtime. The scan afterward is O(n).

So the full algorithm is O(n log n) time and O(n) space if you return the selected subset.

That is usually the fastest practical answer for arbitrary numeric input because any method that avoids sorting still has to recover enough order information to make optimal spacing decisions.

Handling Duplicates and Negative Numbers

Duplicates are handled naturally. If d is nonnegative, duplicate values cannot both be selected because their difference is zero.

Negative values also work without any special logic because sorting places them correctly on the number line.

For example:

print(max_spaced_subset([-5, -4, -1, 0, 3, 8], 2))

The same greedy logic applies.

If You Need Randomness Too

Sometimes "sample" means the result should still feel random. That is a different problem from finding the largest valid subset.

If maximum cardinality is the real goal, use the greedy algorithm above.

If randomness also matters, you need to define the tradeoff explicitly, because a random valid subset is not guaranteed to be the largest one.

That distinction is important. Many implementations become slower and less correct because they mix optimization and randomness without clarifying which objective matters more.

Common Pitfalls

Checking every candidate against every previously selected value is unnecessary once the list is sorted. Comparing only against the last selected value is enough.

Using >= d instead of > d changes the problem definition. The title here says the minimum difference must be larger than the value, so equality should not be accepted.

Trying a random sampling loop to approximate the answer is another common mistake. The greedy sorted solution is exact and faster.

Finally, if the list is empty, return an empty result instead of assuming a first element exists.

Summary

• sort the numbers first, then greedily take the earliest feasible value each time
• this greedy strategy is optimal for maximizing subset size under a strict minimum-spacing constraint
• after sorting, comparing with only the last selected value is sufficient
• the overall time complexity is O(n log n) because sorting dominates
• if you also want randomness, treat that as a different objective from finding the maximum-size valid subset