I want to iterate an array and find all pairs where their difference is 2

This is what i have so far:

var numberOfCases = 5;
var diff = 2;

var input = [1,5,3,4,2];

getPossiblepairs(input);

function getPossiblepairs(input){
    for(cmp in input){
        for(number in input){
            if((input[cmp] - input[number]) == diff){
                console.log("("+input[cmp]+","+input[number]+")");
            }
        }

    }
}

This works but i still feel guilty using two for loops as the bigO is O(n^2) Is this the only way to do this?

I want to iterate an array and find all pairs where their difference is 2

This is what i have so far:

var numberOfCases = 5;
var diff = 2;

var input = [1,5,3,4,2];

getPossiblepairs(input);

function getPossiblepairs(input){
    for(cmp in input){
        for(number in input){
            if((input[cmp] - input[number]) == diff){
                console.log("("+input[cmp]+","+input[number]+")");
            }
        }

    }
}

This works but i still feel guilty using two for loops as the bigO is O(n^2) Is this the only way to do this?

• javascript
• arrays
• performance
• time-plexity

Share Improve this question Follow edited Nov 30, 2014 at 9:05 Scimonster 33.4k1010 gold badges7979 silver badges9191 bronze badges asked Nov 30, 2014 at 9:02 ipalibowhyteipalibowhyte 1,56322 gold badges2222 silver badges3434 bronze badges 5

• There may be algorithms you can do to get better, if you actually know the distribution of numbers (here they are a sequential series, although out of order). But with just 5 entries, so 25 iterations O(5^2), do you really care to get it more efficient than that? – deitch Commented Nov 30, 2014 at 9:05
• I changed the wording to ask for other methods, as 'best way' is going to be closed as primarily opinion based. – Scimonster Commented Nov 30, 2014 at 9:06
• 2 Sort the list whuch is O(N) log n. The one that has a differencee of two from the current one is either the next element, or the one after that. That's an O(1) check. Checking all of them is O(N). So overall O(N log N) – The Archetypal Paul Commented Nov 30, 2014 at 9:09
• @Paul that only works if the numbers aren't repeated – Alnitak Commented Nov 30, 2014 at 9:11
• 1 Another O(N) Pass to put equal elements into counted buckets would fix that. – The Archetypal Paul Commented Nov 30, 2014 at 9:12

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 6

You can do this in O(n log n). Sort the array then go through it in a single pass. Find the difference between the current element and each of the next two, printing out the pair if one is different by 2.

This should work with a n log n plexity:

function getPossiblepairs(input, diff){
    // Create a copy of the original array, so it is not affected by the next operation
    var sortedInput = input.slice();
    // Sort the array
    sortedInput.sort();
    // Iterate through the array, starting from the 0th element
    for (var i=0, n=sortedInput.length; i<n; i++){
        firstNumber = sortedInput[i];
        // Iterate through the array, starting from the (i+1)th element
        for (var j=i+1; j<n && sortedInput[j] <= firstNumber + diff; j++){
            secondNumber = sortedInput[j];
            // if it matches, then log it!
            if (secondNumber - firstNumber == diff){
                console.log('(' + firstNumber + ', ' + secondNumber + ')');
            }
        }
    }
}

See this post for more information about the array duplication.

For usage and testing, see: http://jsfiddle/gycjup5u/2/

do you have memory for a copy of the array? Sort it first, O(n log n), then pick out the pairs in a single O(n) pass.

You can use indexOf() method for every element to determine if an array contains the element greater than given by diff:

function getPossiblePairs(input, diff) {
    for(i in input) {
        var n = input.indexOf(input[i] + diff);
        if(n != -1) {
            console.log("(" + input[i] + "," + input[n] + ")");
        }
    }
}

getPossiblePairs(input, diff);