0

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);
2
  • 1
    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 9, 2012 at 21:26
  • 3
    Also initializing your iteration variable outside the function is highly questionable.
    – Pointy
    Aug 9, 2012 at 21:27

2 Answers 2

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.

1
  • sorry guys, didn't know i needed to accept things, im going back and taking a look
    – Yasir
    Aug 10, 2012 at 1:36
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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.