2
\$\begingroup\$

Here is the function called sumZero, where it should return the sum of any two numbers in the array to sum upto zero. where the array is a sorted array.

My approach: Using 2 pointers approach, calling it as p1 and p2, where p1 points to zero, and p2 points to p1+1. and pointers get incremented

function sumZeroPointers(arr, p1, p2){

    while(p2 < arr.length){

        if(arr[p1] + arr[p2] === 0){
            return [arr[p1] , arr[p2]]
        }else{
            p2++;
            //When the pointer p2 reaches to the end of the array, then increment the pointer p1 by 1, and p2 to p1+1. and continue the while loop matching for the pairs.
            if(p2 == arr.length){
                p1++;
                p2=p1+1;
            }
        }         
    }    
}
function sumZero(array){
  return sumZeroPointers(array, 0, 1)
}
console.log('sumZero  : ', sumZero([-3, -2, -1, 0, 1, 2, 3])) //[-3, 3], indexed at (0, 6)
console.log('sumZero  : ', sumZero([-3, -2, 0, 2, 3])) //[-2, 2], indexed at (1, 3)
console.log('sumZero  : ', sumZero([-4, -2, 1, 2, 3]))//[-1, 1], indexed at (0, 2)

This works all good.

Now there is a another approach were the pointers p1 and p2 are marked at beginning(0) and end of the array (array.length-1), and incremented and decremented based on the sum value.


function sumZero1(arr){
    let left = 0; 
    let right = arr.length - 1;
    while(left < right){
      let sum = arr[left] + arr[right];
      if(sum === 0){
         return [arr[left] , arr[right]]
      } else if(sum > 0){
         right--;
      } else{
         left++;
      }    
    }    
}

console.log('sumZero1  : ', sumZero1([-3, -2, -1, 0, 1, 2, 3])) //[-3, 3], indexed at (0, 6)
console.log('sumZero1  : ', sumZero1([-4, -2, 0, 2, 3])) //[-2, 2], indexed at (1, 3)
console.log('sumZero1  : ', sumZero1([-1, -2, 1, 2, 3]))//[-1, 1], indexed at (0, 2)

this too works well. But in my first approach also I do not see any flaws, readability wise approach 2 makes more sense, as the pointers are made to point at 0 and array.length-1 indexes, and incremented and decremented according to the sum.

What I want to understand is which one to follow, either two pointers pointing to one after another, yields efficient or optimized solution Or the approach 2.

Is there any tips / hints or points I should follow in this 2 pointer problems, like

  1. if the array is sorted, always follow pointer pointing at start and last indexes.
  2. if the array is not sorted , we can keep pointers next to each other or can follow pointer pointing at start and last indexes.

Can you please, let me know if there is any points / hints, I should remember when I follow this 2 pointer approach problems.

basically what I want to know is, is there some more points I should remember while solving 2-pointer problem. or which will be effective.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ In the future, please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Jul 18, 2022 at 13:09

1 Answer 1

1
\$\begingroup\$

Your first algorithm is basically the same as doing this:

for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) { 
        if (arr[i] + arr[j] === 0) {
            return [arr[i], arr[j]];
        }
    } 
}

If you can't see why this is the case, look at you lines here:

//When the pointer p2 reaches to the end of the array, then increment the pointer p1 by 1, and p2 to p1+1. and continue the while loop matching for the pairs.
if(p2 == arr.length){
    p1++;
    p2=p1+1;
}

For every index, i, you are trying the sum against all of the numbers after it.

That gives you a time complexity of O(N^2).

The second algorithm only iterates the array once so it's O(N) and should be much faster for longer arrays than the first option.

Algorithm 1 will work for an unsorted array, algorithm 2 will not.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your replay, you are correct, technically, I am doing the same double for loop, logic, my bad. Can you advise me some points or hits, while approaching 2-pointers problems, like where I have to place my pointers for sorted or unsorted arrays, etc \$\endgroup\$
    – RONE
    Jul 18, 2022 at 9:35
  • \$\begingroup\$ I don't know of any hard and fast rules for this type of problem. Generally, if you see sorted array you can immediately think of binary search, pointers, windows and probably others. Unsorted might prompt you for things like hashsets. To be honest though, I hate these kinds of problems and would only do them for an interview (or prep). \$\endgroup\$
    – RobH
    Jul 18, 2022 at 9:50

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.