5

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?

Scimonster
  • 32,893
  • 9
  • 77
  • 89
ipalibowhyte
  • 1,553
  • 2
  • 22
  • 34
  • 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 Nov 30 '14 at 09:05
  • I changed the wording to ask for other methods, as 'best way' is going to be closed as primarily opinion based. – Scimonster Nov 30 '14 at 09: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 Nov 30 '14 at 09:09
  • @Paul that only works if the numbers aren't repeated – Alnitak Nov 30 '14 at 09:11
  • 1
    Another O(N) Pass to put equal elements into counted buckets would fix that. – The Archetypal Paul Nov 30 '14 at 09:12

4 Answers4

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.

Allen Luce
  • 7,859
  • 3
  • 40
  • 53
  • 1
    what he said. beat me by a minute – Andras Nov 30 '14 at 09:10
  • @Doug i'm currently trying to implementing your solution, but wouldn't the difference between each next two element always remain 1 ? – ipalibowhyte Nov 30 '14 at 09:58
  • 1
    Hi @Pizzy213codes, with your example, after the sort phase there'd be [1, 2, 3, 4, 5]. The first step is to compare 1 to 2 and 1 to 3. The diff is 1 in the first case, 2 in the second. If there were any non-consecutive numbers like [1, 5, 7, 22], then the differences will get bigger. I'm guessing you figured it out, though! – Allen Luce Dec 02 '14 at 01:09
4

This should work with a n log n complexity:

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.net/gycjup5u/2/

Community
  • 1
  • 1
Mathieu Rodic
  • 6,637
  • 2
  • 43
  • 49
3

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.

Andras
  • 2,995
  • 11
  • 17
2

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);
akarilimano
  • 1,034
  • 1
  • 10
  • 17