How to find the minimum difference between 2 numbers inside an array of n size (find smallest interval) in PHP

After trying to solve an exam for a job, I found an interesting question that seems to be very basic, but without the right implementation you may end up in trouble. The problem is the following one, you need to find the minimum difference or smallest interval of the numbers inside an array. For example:

// From the given array
[1, 5, 3, 19, 18, 25]
// The smallest interval or minimum difference is: 1
// Because that's the difference between the 2 
// closest numbers in the array (numerically speaking)
// in this case 18 and 19 (19-18=1)

It's very probable that you may think that a possible solution would be to find the 2 smallest number elements in the array, so you can find the difference and therefore the interval, however with the following case:

// Input:
[80, 1, 4, 25, 12, 60, 78, 70]
// Result: 2
// Difference between 78 and 80

It won't work as the smallest interval, in this case, is 2 (interval between 78, 80) and the interval between 1 and 4 is 3. So, the proposed solution won't work. In this article, I'm going to explain to you how to easily find the smallest interval or difference between the numbers of an array in PHP optimally.

Implementation

So, the current problem requires an optimal solution, otherwise, with huge arrays, the performance will be messy. The ideal thing to do is to sort the array in ascending order, using the sort function of PHP. This will allow us to iterate over the array and find the minimum difference by simply comparing every ascending pair in the given array. The following image representation will display exactly what we are going to do with the input array of 8 items:

• Set the input array, in this case, there are 8 items in different numerical order.
• Sort the array, which will generate the same array of 8 items but starting with the lowest number and increasing respectively.
• Then, create pairs with the iteration index of a loop, for example, 1 and 4, 4 and 12, 12 and 25, and so on with all the items.
• Subtract the smallest number from the largest number in the pair, this will generate the interval.
• Store in a variable the difference generated by every operation and update it only if the result is lower than the previous one, once it ends, the variable will store the smallest interval, which in this case is 2.

Having said that, writing this logic in PHP code, our snippet looks like this:

/**
 * Find the smallest interval (minimum difference) between the numbers of an array.
 * 
 * @param array $numbers
 * @return {Int} $diff
 */
function findSmallestInterval(array $numbers)
{
    // Number of items in the array
    $length = count($numbers);

    // Sort array in ascending order
    sort($numbers);

    // Initialize difference with the max integer allowed by PHP in the constant
    // Usually int(2147483647) in 32 bit systems and int(9223372036854775807) in 64 bit systems
    $diff = PHP_INT_MAX;

    // Find the smallest interval comparing the adjacent pairs in the sorted array
    for ($i = 0; $i < $length - 1; $i++){
        if ($numbers[$i + 1] - $numbers[$i] < $diff){
            $diff = $numbers[$i + 1] - $numbers[$i];
        }
    }

    return $diff;
}

These are some items that you can test with this implementation:

$items = [80, 1, 4, 25, 12, 60, 78, 70];

// Expected: 2
echo findSmallestInterval($items);

$items = [1, 5, 3, 19, 18, 25];

// Expected: 1
echo findSmallestInterval($items);

$items = [1, 19, -4, 33, 38, 25, 100];

// Expected: 5
echo findSmallestInterval($items);

Happy coding ❤️!