Another way to get all combination of integers of an array Javascript

Question

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?

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
– 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
– Scimonster, Commented Nov 30, 2014 at 9:06
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
– The Archetypal Paul, Commented Nov 30, 2014 at 9:09
Another O(N) Pass to put equal elements into counted buckets would fix that. — The Archetypal Paul
– The Archetypal Paul, Commented Nov 30, 2014 at 9:12

Allen Luce · Accepted Answer · 2015-04-08 20:00:07Z

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.

edited Apr 8, 2015 at 20:00

answered Nov 30, 2014 at 9:08

Allen Luce

8,4794 gold badges48 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andras Over a year ago

what he said. beat me by a minute

ipalibowhyte Over a year ago

@Doug i'm currently trying to implementing your solution, but wouldn't the difference between each next two element always remain 1 ?

Allen Luce Over a year ago

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!

Community · Accepted Answer · 2017-05-23 11:43:36Z

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/

edited May 23, 2017 at 11:43

CommunityBot

11 silver badge

answered Nov 30, 2014 at 9:21

Mathieu Rodic

6,7702 gold badges45 silver badges49 bronze badges

14 Comments

The Archetypal Paul Over a year ago

That's order n^2. And worse than the original in run time (it does length^2 comparions, like the original, but sorts as well)

Mathieu Rodic Over a year ago

Yeah, my (corrected) typo was totally worth a "-1".

The Archetypal Paul Over a year ago

That;s still n^2. So, yes, it was

Mathieu Rodic Over a year ago

No it isn't. The second iteration starts at i+1!

The Archetypal Paul Over a year ago

Edited with the extra condition, and changed my -1 to +1 (since your answer did give code...)

|

Andras · Accepted Answer · 2014-11-30 09:09:52Z

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.

answered Nov 30, 2014 at 9:09

Andras

3,05515 silver badges17 bronze badges

Comments

akarilimano · Accepted Answer · 2014-11-30 09:31:56Z

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);

answered Nov 30, 2014 at 9:31

akarilimano

1,0741 gold badge11 silver badges18 bronze badges

2 Comments

The Archetypal Paul Over a year ago

Which is, of course, O(N^2). So the OP will still feel guilty :)

akarilimano Over a year ago

@Paul yes, this is my fault, didn't notice the optimization request, just thought of another way of doing it.

Collectives™ on Stack Overflow

Another way to get all combination of integers of an array Javascript

4 Answers 4

3 Comments

14 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

14 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related