Finding the smallest difference in a list of numbers

Lately I've been playing around with programming puzzles and challenges as a method for both killing time, and for trying out new programming languages that I haven't had a chance to use in a professional or hobby setting. Right now my favorite site for these is CodinGame, which I've been spending a lot of my spare time on.

The challenges are fun and interesting, and I was surprised to find that they've pushed me to improve my programming skills. As a self-taught developer, I've certainly implemented my fair share of algorithms, but I couldn't tell you the name of most of them. That's where these puzzles and challenges come in: most puzzles are oriented around a certain type of algorithm, and its up to you to first solve and then optimize it.

I've got a few complaints with the site I'm using right now -- chiefly that solutions are often rewarded for being as short and in as few lines of code as possible (which can sacrifice readability) -- but all in all the simpler challenges are a great way to kill an hour of time and feel good about yourself afterwards.

One of the "simpler" challenges I've done in the past couple of days revolved around taking a list of integers and finding the shortest distance between any two numbers in the list. So if you have a list of [4, 6, 10] you'd be expected to print 2 because 6-4=2 is the smallest difference between all numbers in the list. Just looking at this challenge it seemed almost too easy. Since I was doing the challenge in TypeScript at the time, I wrote out a small reducer function to loop through the array and keep track of the smallest difference.

It looked something like this:

const numbers: number[] = [...]
const absDifference = (a: number, b: number) => Math.max(a, b) - Math.min(a, b);
const smallestDiff = numbers.reduce<number | null>((state, num) => {
    const latestDiff = numbers.filter(i => i !== num).reduce((innerState, innerNum) => {
        const diff = absDifference(num, innerNum);
    
        return innerState === null ? diff : Math.min(innerState, diff);
    }, null); 

    return smallestDiff === null ? latestDiff : Math.min(smallestDiff, latestDiff);
}, null);

Right off the bat this is already more complicated than it needs to be, but I have a habit of always reaching for a reducer function whenever I need to do something with an array. The fact that this reducer function is actually two reducer functions should be a red flag that this could be simplified, but it does work and finds the smallest difference between any two numbers in the array.

However, just because this function works doesn't mean it's free of some serious performance problems. For every number in the array, the function is looping through the array two additional times. First when it filters out the number it's currently looking at (.filter(i => i !== num)), and then again when it calls that inner reduce function to try to find the smallest difference between the current number and all other numbers.

Those loops and calculations add up very quickly, and when you have 999999 numbers in the list (like this challenge I was doing had), you spend far too much time looping, doing billions of operations in total. In the challenge I was doing, my solution did not meet the performance requirement and it failed the test.

The solution

That's when I took a closer look (and a quick Google search) and realized there's a far more simple way to calculate the smallest difference. If you sort the list from smallest number to largest, you only need to loop over it once, and only need to calculate the difference between the next number and the current number. That's much, much easier than calculating the difference between the current number and all numbers, and then trying to find the smallest one, and then figuring out if that smallest difference is smaller than the overall smallest difference up to that point.

The solution is super simple and I honestly facepalmed when I realized how overly complicated I had made it. (Presented below in the four different programming languages I've been completing these challenges with lately.)

TypeScript:

const numbers: number[] = [...].sort((a, b) => a - b);
let smallestDiff: number | null = null;

for (let i = 0; i < numbers.length - 1; i++) {
    // Only calculate the difference between the next number and the current
    const latestDiff = numbers[i + 1] - numbers[i];

    // Only keep the diff if it's smaller than any we've seen up to this point
    smallestDiff = smallestDiff === null ? latestDiff : Math.min(smallestDiff, latestDiff);
}

console.log(smallestDiff);

C#:

List<int> numbers = ...;
int? smallestDiff = null;

numbers.Sort();

for (int i = 0; i < numbers.length - 1; i++) 
{
    // Only calculate the difference between the next number and the current
    int latestDiff = numbers[i + 1] - numbers[i];
    
    // Only keep the diff if it's smaller than any we've seen up to this point
    smallestDiff = smallestDiff.HasValue ? Math.Min(smallestDiff.Value, latestDiff) : latestDiff;
}

Console.WriteLine("{0}", smallestDiff);

Dart:

List<int> numbers = List.generate(count, ...)..sort();
int smallestDiff = null;

for (int i = 0; i < numbers.length - 1; i++) {
    // Only calculate the difference between the next number and the current
    int latestDiff = numbers[i + 1] = numbers[i];

    // Only keep the diff if it's smaller than any we've seen up to this point
    smallestDiff = smallestDiff === null ? Math.min(smallestDiff, latestDiff) : latestDiff;
}

stdout.writeln(smallestDiff);

F#:

let numbers = 
    ...
    |> Seq.sort
let totalNumbers = Seq.length numbers
let mutable smallestDiff: int option = None

for i = 0 to (totalNumbers - 1) do
    let num = Seq.item i numbers
    let nextNum = Seq.item (i + 1) numbers
    let latestDiff = nextNum - num
    
    smallestDiff <-
        match smallestDiff with 
        | Some smallest -> Math.Min(smallest, latestDiff)
        | None -> latestDiff
        |> Some
        
printfn "%A" smallestDiff

The important thing is to, no matter which language you're using, remember to sort the numbers first! If you sort them from smallest to largest, you only need to worry about calculating the difference between the next number in the list and the current one.