# Intro to Algorithms: Two Pointers Technique

## A detailed primer on an essential technique

In my last post, I covered the ins and outs of the Binary Search algorithm. The binary search method assumes that the collection you are browsing has already been sorted, and the two pointers technique is no different. However, whereas binary search locates a single element within a collection, the two pointers technique is used to locate two elements within an array that together meet a condition. Let’s take a look at how it works.

# Charging Ahead: A Naive Solution

Let us turn to a brute force, naive solution to a problem where the two pointers technique might be better suited.

Given an array of integers (already sorted in ascending order) find and return the indices of the two elements that, when added together, are equal to the provided target value.

Or given an `array`

and a `target`

, write an algorithm that solves for `array[i] + array[j] === target`

.

How might we devise a brute force approach to this problem? Well, the first step would be to iterate through each element in the array. Then we would have to check each *selected* element with the *remaining* elements in our collection, testing if their sum matches the target value. Sounds like a job for some nested loops.

This solution does *technically* work, but it’s woefully inefficient. You have to iterate through the entire array for each element in the array until the solution is found! This might not sound terrible if the array is three or four elements long. But imagine doing this with an array that’s one million elements long. You’d have to count to one million (technically 999,999) before you’d even progress to the second element! Think about how long that would take if our solution was to be found in the last two elements in the array.

This method has a Big O notation of O(n²), meaning that as the size of our array grows, the time it takes to find our answer grows *exponentially*. Not ideal at all. How might we devise a better solution?

# Implementing Two Pointers

Let’s take a second look at the problem’s description:

Given an array of integers (

already sorted in ascending order) find and return the indices of the two elements that, when added together, are equal to the provided target value.

How can we leverage this information to construct a more efficient algorithm? With this knowledge, we know that incrementing the index *always* increases the current element's value, and decrementing the index will *always* do the opposite.

In the previous solution, we were always incrementing indices, with our second pointer, `j`

, given the value of `i + 1`

and then iterating through the remaining elements. Instead, we can have `j`

point to the *last element* of the array and add in some conditional logic.

# Approaching the Base Case

Our conditional logic will need to identify our *base case(s)*—the terminating scenario(s) that exits our function. That’s pretty simple with our current example.

Given an array of integers (already sorted in ascending order) find and

return the indices of the two elements that, when added together, are equal to the provided target value.

So our base case is `array[i] + array[j] === target`

. When that condition is met we can exit our function and return `[i, j]`

as the indices that solve our problem. How might we navigate from our position in the previous code example towards that base condition?

There are two ways that we can fail to satisfy the conditions for our base case*. **The sum of **array[i]** and **array[j]*** will either be greater than or less than our target value.** Combine that with what we know about incrementing and decrementing indices and we’ve got all we need to solve our problem.

** If the sum of the two elements is greater than the target, decrementing one of the indices will bring us closer to our goal**. The inverse is also true.

**Which index should we choose for which operation?**

*If the sum of the two elements is less than the target, incrementing one of the indices will steer us in the right direction.*Our first pointer, `i`

, starts out at 0, so it’d be pretty hard to decrement it any further (let’s just ignore negative indices for now, as they’re not at all relevant or helpful with our current problem). Similarly, our second pointer, `j`

, starts out at `array.length — 1`

or the last possible index. If we increment `j`

we end up pointing to an element that does not exist! No Bueno.

**Behold The Two Pointers**

Looking over our completed algorithm, you can clearly see that it’s significantly more efficient than a brute force approach. At worst, the function will iterate over every element in the given array, giving this function O(n) time complexity. That means our improved function is exponentially faster when compared to the O(n²) complexity of a brute force approach. Quite an improvement!

# Recap

To review, the two pointers technique is useful when searching for a pair of elements within an array that meet a specific condition (i.e. *base case*). We then evaluate the ways that the two elements can fail to meet the base condition and write conditional logic that will get us closer to our goal.

The two pointers technique is not an algorithm but rather a *technique, *meaning there are a variety of ways it can be used. The underlying principle, however, is an important one. Using two (or more) pointers allows us to traverse and process data much more efficiently than a brute force approach. What other scenarios might this technique be found useful? How else could you write the solution provided above? (Perhaps the focus of future blog posts?)

If you found this article helpful please think about subscribing or sharing it amongst your colleagues. Much thanks, and happy coding!

Resources:Two Sum II - Leetcode Challenge #167The inspiration for this write upTwo Pointers Technique - Geeks for GeeksGrokking Algorithms: An Illustrated Guide for Programmers and Other Curious People