# Multiple Pointers Pattern

Before delving into classic algorithms and data structures, we must learn or revisit some problem-solving patterns. The Multiple Pointers pattern will be our starting point.

The main idea here is to create multiple pointers attached to specific positions and move them based on a particular condition.

You can find Multiple Pointers In countless algorithms, like:

* Binary Search
    
* Quick Sort
    
* Merge Sort
    
* Etc.
    

Let's imagine we need to write a function that finds the first pair where the sum is 0 from a given SORTED array. `E.g., [-5, -1, 0, 2, 5] //-5 + 5`

Instinctively, we write something like the following:

```jsx
function pairSum(arr) {
	for (let i = 0; i < arr.length; i++) {
		for (let j = 0; j < arr.length; j++) {
			if (arr[i] + arr[j] === 0) return `${arr[i]} + ${arr[j]}`;
		}
	}
}
```

The big problem here is that our time complexity is quadratic O(n^2) because we walk through the array twice. But, we can solve it by using Multiple Pointers to walk through the array only once:

```jsx
function pairSum(arr) {
  let left = 0;
  let right = arr.length - 1;

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

  return null;
}

```

Now, we have a linear time complexity O(n).

Let's get deeper into the above solution:

* We set up two pointers: `left` with the initial position and `right` with the last position.
    
* The loop will be running until `left < right`.
    
* We store the first sum.
    
* If `sum === 0`, we found our pair.
    
* If not and `sum < 0`, we will move our `left` pointer to the right by incrementing it.
    
* If `sum > 0`, move the `right` pointer to the left by decrementing it.
    
* If nothing was found, return `null`.
    

Let's suppose we have the following SORTED array:

`[-6, -5, -1, 0, 2, 3, 4, 5, 10]`

```jsx
1.
[-6, -5, -1, 0, 2, 3, 4, 5, 10]
  ^                          ^
 left                      right
 
 sum = -6 + 10 = 4
 
 As 4 > 0, we move our right pointer to the left
 
 [-6, -5, -1, 0, 2, 3, 4, 5, 10]
   ^                      ^
 left                   right
 
 sum = -6 + 5 = -1
 
 -1 < 0, we move the left pointer to the right
 
 [-6, -5, -1, 0, 2, 3, 4, 5, 10]
	   ^                  ^
      left              right

sum = -5 + 5 = 0

Pair found: -5, 5.
```