How to Reduce Two Loops in Javascript for Efficiency

Question

I have a particular array, by which I wanted to check if two values within the array equal the value passed into the function, and if the two integers do, then pass it into a new array.

I have solved this by using two backwards while loops and caching the length as a variable, which seemed to be efficient. However, someone mentioned to me there might be a way to remove the need for one of the loops and making it much more efficient and thus optimizing the BIG O notation.

Any ideas how this could be done? This is what I have...

var intArray = [1, 3, 7, 8, 10, 4, 6, 13, 0],
    newArray = [],
    i = intArray.length;


function arrayCheck(k) {
    while(i--) {
        var z = i;
        while (z--) {
            if (intArray[i] + intArray[z] === k) {
                newArray.push(intArray[i]);
                newArray.push(intArray[z]);
            }
        }
    }
    alert(newArray);
}

arrayCheck(8);

There are always going to be n * (n-1) pairs, but you could pre-compute the sums only when the original array changes. — Pointy
– Pointy, Commented Aug 9, 2012 at 21:26
Also initializing your iteration variable outside the function is highly questionable. — Pointy
– Pointy, Commented Aug 9, 2012 at 21:27

Community · Accepted Answer · 2017-05-23 10:34:39Z

2

There is an algorithm that solves this problem in linear [O(n)] time. I recommend you check out this SO answer.

Also, as others have stated, marking answers as accepted will make people more likely to answer your questions. You may wish to revisit questions you've previously asked and accept any answers that deserve it.

edited May 23, 2017 at 10:34

CommunityBot

11 silver badge

answered Aug 9, 2012 at 21:37

Zach

2,4411 gold badge17 silver badges21 bronze badges

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

1 Comment

Yasir Over a year ago

sorry guys, didn't know i needed to accept things, im going back and taking a look

Pedro L. · Accepted Answer · 2012-08-09 22:06:38Z

1

if you check for number N, and intArray[i] = M, then you need to find a value N-M in the array.

Build an efficient tree search to find values N-M and you can solve this in O(n+logn).

answered Aug 9, 2012 at 22:06

Pedro L.

7,6063 gold badges28 silver badges27 bronze badges

Collectives™ on Stack Overflow

How to Reduce Two Loops in Javascript for Efficiency

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related