What is the fastest algorithm to find the minimum difference between pairs of numbers in an array? [duplicate]

Question

Possible Duplicate:
Is it possible to find two numbers whose difference is minimum in O(n) time

For example, in [4, 2, 7, 11, 8], the algorithm should return abs(7-8) = 1.

The brute force way will be O(n²) and sorting will give O(nlogn). Is there more efficient way?

Thanks

Answer 1

I think sorting and comparing is going to be your best bet. Something like:

function minDiff( arr ) {
    var min,
        temp,
        initDiff = false,
        arr = arr.sort( function(a, b){return a-b} ),
        last = arr.length - 1,
        i;

    for ( i = 0; i < last; i++ ) {

        if ( !initDiff ) {            
            min = arr[i + 1] - arr[i];
            initDiff = true;
        } else {            
            temp = arr[i + 1] - arr[i];

            if ( temp < min ) {            
                min = temp;            
            }            
        }
    }

    return min; 
}

var myArr = [ 1, 8, 5, 96, 20, 47 ],
    min = minDiff( myArr );

console.log( min ); // 3

Answer 2

A similar question here - Is it possible to find two numbers whose difference is minimum in O(n) time . It appears to be O(nlogn).

This page may give useful background info too.