Error in finding minimum absolute difference between any two pair of elements in an array using javascript

Question

I am trying to solve a program for finding minimum absolute difference between any pair of elements in an array using javascript. The input takes arguments as array elements. The output returns the minimum absolute difference between any two elements in an array

For example, input as [1,2,4] and the output is 1

The detailed description of the problem is given in this link.

In my code, when giving input array containing 1000 elements, it compiles and shows Terminated due to time out, but it works for smaller sized input arrays

I think the error comes from the issues in performance and complexity . I researched for issue but I'm stuck with how to proceed further steps

My code:

    var arr = [..] //array containing 1000 elements
    var count = minimumAbsoluteDifference(arr);
    console.log(count);
    function minimumAbsoluteDifference(arr) {
        var diff = []; var index = 0;
        arr.sort((a, b) => { return (a - b); });
        for (var i = 0; i < arr.length-1; i++){
            for (var j = i+1; j < arr.length; j++){
                if (i != j) {
                    diff[index] = Math.abs(arr[i] - arr[j]);
                    console.log("index", i, j);
                    index++;
                }
            }
        }
        var minAbsoluteDifference = Math.min(...diff);
        return minAbsoluteDifference;
    }

Answer 1

After the array has been sorted, the minimum absolute difference between any two elements will necessarily be between two adjacent elements. So, you can change your nested for loops (O(N^2)) to a single for loop (O(N)) (though, the sort function is still O(N log N), so overall complexity is only reduced to O(N log N)):

function minimumAbsoluteDifference(arr) {
    var diff = [];
    arr.sort((a, b) => a - b);
    for (var i = 0; i < arr.length - 1; i++) {
        if (i < arr.length - 1) {
            diff.push(Math.abs(arr[i] - arr[i + 1]));
        }
    }
    var minAbsoluteDifference = Math.min(...diff);
    return minAbsoluteDifference;
}

This would work in most situations, but another issue is that HackerRank appears to call this function with unreasonably huge arrays (eg, with 100000 items in a single array), so

Math.min(...diff)

will result in

RangeError: Maximum call stack size exceeded

Call Math.min on every iteration instead:

function minimumAbsoluteDifference(arr) {
    var lowestDiff = Infinity;
    arr.sort((a, b) => a - b);
    for (var i = 0; i < arr.length - 1; i++) {
        lowestDiff = Math.min(lowestDiff, Math.abs(arr[i] - arr[i + 1]));
    }
    return lowestDiff;

}