Another way to get the whole combination of integers of a Javascript array

Question

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

This is what I still have:

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 about using two for loops, since bigO O (n ^ 2) . Is this the only way to do this?

Answer 1

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

Answer 2

This should work with complexity n log n:

 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 on array duplication.

For use and testing see: http://jsfiddle.net/gycjup5u/2/

Answer 3

Do you have memory for copying an array? First sort it, O (n log n), then select the pairs in one pass O (n).

Answer 4

You can use the indexOf() method for each element to determine if the array contains an array other than 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);