*The Two Pointer Pattern*

This will be the first post in a series where I will cover common coding patterns used for solving LeetCode and whiteboard questions. These types of questions can be challenging even for the most seasoned developer. However, by knowing common patterns that can be utilized when solving these problems, you’ll go from zero to hired in no time.

This pattern involves two pointers (or references) used in order to more efficiently iterate through a data set. The pointers will work together to iterate through the data until a predefined target condition is reached. The data set is often a standard array (strings and linked lists are also applicable). It’s very suitable when asked to identify certain patterns in the data, such as:

- Are there duplicate entries in the array?
- Given a string, return the string in reverse
- Are there two elements in the array that sum to a target value? This is most famously known as the Two Sum problem.

Generally speaking, you’ll know to use some form of this technique when any of the following are true:

- The data is already sorted
*or*you’re allowed to sort the data and having it sorted can be beneficial to your solution - The solution is expected to return a pair/triplet of elements or even a subarray of the original array

However, the major advantage that the two pointer pattern provides is in terms of time and space complexity. A solution that utilizes this pattern will usually lead to a time complexity of *O(n)* and space complexity of *O(1)*. This is a huge win compared to alternative, brute force solutions that provide time complexities of *O(n ^{2})* and space complexities of

*O(n)*.

### The Two Sum Problem

Hopefully by this point, I’ve convinced you of the importance and power behind the two pointer pattern. However, to better frame these advantages, we’ll use a very common whiteboard question, which is the aforementioned Two Sum problem:

Given an array

numsand an integertarget, find two indices withinnumswhose elements sum up totarget. You may assume that each input will have a unique solution and you cannot use the same element twice. For example:

nums =[1, 2, 3, 4, 5]

target = 5

output =[0, 3]

Let’s solve this problem first using a brute force approach and then the two pointers pattern to highlight its advantages. All code samples are written in Kotlin.

#### Brute Forcing the Sums

Any developer, whether a recently hired junior or a seasoned senior, would likely fall back to the brute force approach if they didn’t know about two pointers (or any other patterns). With the pressure and heat of the interview steadily rising and your time dwindling away, you’ll have no choice but to resort to using brute force to have some sort of solution:

```
fun twoSumBruteForce(data: IntArray, target: Int): IntArray {
for ((firstIndex, firstNumber) in data.withIndex()) {
for ((secondIndex, secondNumber) in data.withIndex()) {
// Skip any duplicate entries
if (firstIndex == secondIndex) {
continue
} else if ((firstNumber + secondNumber) == target) {
return intArrayOf(firstIndex, secondIndex)
}
}
}
return intArrayOf()
}
```

This solution does work, but there are certainly several drawbacks:

- The nested for-loops are indicative that the time-complexity is indeed
*O(n*^{2}) - Related to the previous point, this solution does not scale. As the input size increases, the amount of time to process the data will increase exponentially

Space complexity isn’t compromised, which at least is a benefit. But there must be a better solution 🤔

#### Two Pointer Teamwork to the Rescue

As you likely have guessed, we can reduce our time complexity for this problem if we utilize the two pointer technique. First, we’ll have to sort the array (most languages and/or frameworks provide this out of the box). Next, we’ll create our two pointers. The first, called *low*, will refer to the first element of the array. The other pointer, called *high*, will refer to the last element. Before diving into the code, let’s take a look at what this gives us with all of these tools on hand (sorted array with two pointers):

It may not be immediately obvious what these tools provide us. However, as a starting point, one thing we can do is sum up the elements that *low* and *high* are pointing to, which gives us 6. Another thing that we know is that in their initial state, *low* points to the lowest value in the array and vice versa for *high*. Now let’s recap what we know so far:

- The input array has been sorted
- The two elements that
*low*and*high*refer to sum to a value greater than our target of 5 *low*and*high*point to the lowest and greatest values in the array, respectively

Therefore, we can conclude that we need to find a pair of elements that sum to a value *less* than the sum we’ve found so far. How can we find such a sum, using just the pointers we have? One option is to move *low* one element to the right while keeping *high* in its current position:

Summing up the elements of *low* and *high* gives us… 7 🤔 Upon further inspection, you’ll notice that moving *low* across the array will give us higher and higher sum values. And this is exactly what we expect since the array has already been sorted. If we know that, then the opposite should be true if we move *high* one element to the left:

**Eureka!** That gives us the target that we’re looking for. This means that we can adjust *high* and *low* as we determine candidate indices for our answer. Our constraints will be:

- If the sum is less than the target value, move
*low*one element to the right: this will provide the next highest candidate sum - If the sum is greater than the target, move
*high*one element to the left: this will provide the next lowest candidate sum

All that’s left is to throw this logic into some sort of a loop so that we can iterate over the array. We will likely want to continue making comparisons between *low* and *high* until they’re equal since we can’t use the same element twice in our output. With all of this in mind, let’s code up this bad boy:

```
fun twoSumTwoPointers(data: IntArray, target: Int): IntArray {
var low = 0
var high = data.size - 1
while (low < high) {
val candidateSum = data[low] + data[high]
if (candidateSum == target) {
return intArrayOf(low, high)
} else if (candidateSum < target) {
low++
} else {
high--
}
}
return intArrayOf()
}
```

The advantages of this approach should be quite clear. In terms of space complexity, it remains *O(1)*, same as our brute force solution. However, the real advantage this has is in terms of time complexity. As we move the *low* and *high* pointers, they will only iterate through the array for a maximum of *n* times (the *while()* terminates once the pointers are equal). This algorithm will iterate *n*-times if:

*high*remains in place and*low*continuously moves to the right or*low*remains in place and*high*continuously moves to the left or- the sum does not exist and low and high both gradually move to the center

Therefore, we can conclude that the time complexity is simply *O(n)*, which is a huge win over the *O(n ^{2})* brute force approach.

### Two Pointers for the Win

In this first post, I hope that I’ve gotten you excited and motivated to start using the two pointer pattern. It’s a technique that I’ve seen used very frequently in whiteboard-like questions and can be used to solve some intricate, complex problems. Stay tuned for my next coding pattern post. In the mean time, go score some two pointers:

Happy coding everyone!