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, Aug 09 '12 at 21:26
Also initializing your iteration variable outside the function is highly questionable. — Pointy, Aug 09 '12 at 21:27

score 2 · Accepted Answer · edited May 23 '17 at 10:34

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 '17 at 10:34

Community

1
1

answered Aug 09 '12 at 21:37

Zach

2,441
1
16
20

sorry guys, didn't know i needed to accept things, im going back and taking a look – Yasir Aug 10 '12 at 01:36

score 1 · Answer 2 · answered Aug 09 '12 at 22:06

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 09 '12 at 22:06

Pedro L.

7,376
3
25
27

How to Reduce Two Loops in Javascript for Efficiency

2 Answers2