Algorithms - Two Pointers Pattern
Published: 2022-06-27 22:41:50

This covers the Two Pointer Pattern algorithm for technical interviews in JavaScript.

##When to Use the Two Pointer Pattern
The Two Pointer Pattern is helpful when you need to perform a search to find a pair of numbers that meet a certain condition within a sorted data set. 

For example, you can use this method to solve to find the first two numbers in an array that sums to a desired value.

The Two Pointer Pattern only works if your data set is **sorted**. Be sure to ask your interviewer if the data set is already sorted or if it can be.

##How to Use the Two Pointer Pattern
Let's assume you are solving to find the first set of numbers that sum to zero in a sorted array. 

Instead of using brute force and nested loops to check the 1st item with the 2nd, then the 1st item with the 3rd and so on, you can set up pointers in the first (left) and last (right) position of the array to compare.

![steps to solve for sum of 3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a6n74amn8xwedyol6wz1.png)

Move the pointers based on the sum of the values:
- If the sum of the pointers are greater than the solve for 0, it means the highest number is too large, so move the last pointer (right) down 1 position. 
- If the sum of the pointers are less than the solve for 0, it means your smallest number is too small, so move the first pointer (left) up 1 position. 

Repeat this logic until the pointers meet or you solve for the desired sum.

###Hasn't clicked yet?
If the biggest number (right pointer) is paired with the smallest number (left pointer) and their sum is _greater than_ the desired value, then no other number paired with the right pointer will result in the desired sum as it will continue to be too high. So, move the right pointer one position over towards the center, keep the left pointer the same, and run through the iteration again.

The same idea applies if the sum of the pointers is too small - you move the left pointer over one spot towards the center. If the sum of smallest number (left pointer) and largest number (right pointer) is _less than_ the sum, then there is no number remaining in the array that can be paired with the smallest number to meet your desired sum - since even paired with the highest number is too low.

##Visual Examples
In this example, we solve for the first pair that sums to 0. Notice that the data set is sorted from smallest to largest. 

If you take the first number at index 0 (-3) and the last number at index 6 (3), you'll find the answer in one iteration - the sum equals zero!

![steps to solve for sum of 0](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7k3kh5krmgpw3j8go9i8.png)

---

What if you are solving for the first pair that sums to 2? This completes in 3 iterations.
![steps to solve for sum of 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/reg3uc3yuypzoqi2d7st.png)

---

Here's another example, solving for sum of 10. Completes in 5 iterations:
![steps to solve for sum of 10](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3ro6vy74xdpzrjp6aaz3.png)

---

Last example, solving for sum of 30. Here, the solution is not found and it uses the max amount of iterations, 4:
![steps to solve for sum of 30](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iduy5djpcf6slb90p0br.png)

##How to Code Two Pointer Solution
Example: return an array of the first pair that sums to zero.

```
function zeroSum(arr) {
   let left = 0;
   let right = arr.length - 0;

   while(left < right){
      let sum = arr[left] + arr[right];
      if (sum === 0){
         return [[arr[left], arr[right]];
      } else if (sum > 0){
         right --;
      } else {
         left ++;
      }
   }
}
```

###Explain the Code Line by Line
```
function zeroSum(arr) {
  ...
}
```
- Declare the JavaScript function, passing in `arr` as a parameter for a data set.

---

```
   let left = 0;
   let right = arr.length - 0;
```

- Here we declare our pointer's initial index. 
- The `left` pointer will always start at 0, since an array's index starts at 0. 
- The `right` pointer starts at the last index in our array, which we find by getting the array length and subtracting by 1 to get it's index.

---

```
   while(left < right){
     ...
   }
```
- We set our loop to run only while our `left` pointer is less than our `right` pointer. Otherwise we'd duplicate iterations if our `left` pointer is greater than or equal to the `right` pointer.

---

```
      let sum = arr[left] + arr[right];
```
- We declare `sum` inside the `while` loop so that the respective pointers update on each iteration.
- The `sum` equals the value at the `left` pointer's index plus the value at the `right` pointer's index.

---

```
      if (sum === 0){
         return [[arr[left], arr[right]];
      } else if (sum > 0){
         right --;
      } else {
         left ++;
      }
```
- The `if` statement sets the pointers based on our condition. 

- First, if the `sum` equals 0, then return the values in an array itself. This `return` will exit the `while` loop on the first iteration that matches our criteria. 

- If `sum` is greater than 0, then the numbers are too large. Decrease the `right` pointer one space to the left.

- Else (if `sum` is less than 0), then the numbers are too small. Increase the `left` pointer one space to the right.

## Big O of the Two Pointer Pattern
Using brute force with nested loops gives a time complexity of O(n^2) as you have to loop through each item in the array to grab the 1st number, then loop again through each item to check it against the 2nd. 

Using the Two Pointer Pattern reduces the time complexity to be more favorable at O(n). This pattern will at most only iterate the length of the array minus 1, since we compare in pairs.

Space to solve this problem will be constant at O(1).