Using The Two Pointer Method

The two point method is commonly used with array problems. Lets take a beginner algorithm problem and see how we can use it:

Two Sum

The brute force way is to iterate through each number of the array and add it individually with every number after it, and then match it with the desired sum. This would result in O(n²). This is what it would look like:

With the two pointer method, we can place two pointers (exactly what the name says) at the beginning (left pointer) and ending(right pointer) indices of an array. We would check if the sum of two number equal X. If the sum is greater than X, we’ll move the right pointer one index to the left. If the sum is less than X, we’ll move the left point one index to the right. We would keep doing this until we get a sum equal to X, or when the two pointers meet and we don’t have a sum equal to X.

The code below is how we would implement the two pointer method in Javascript. With this, we reduced our run time to O(n).

Going back to my previous blog, we learned how to evaluate and measure an algorithm. We came across a sorted square problem.

We know the brute force or the easiest method we can think of is to square the array and call .sort() on the the new array to get desire outcome. Yes its the quickest way to get the solution, but based on the speed of the algorithm (O(n log(n)), we can be more efficient.

Example Arrays

Now with the two pointer method in example 1, we can place one pointer(right pointer) on the first positive number (0), and the left pointer on the first negative number. We would square both numbers and put the number with the lower value in the new array. If the number that was smaller is on the right, we will then move the right pointer on index to the right. If the number was on the left, then vice versa. We would repeat this while loop until we have iterated through the whole array and created a new sorted square array. Below is the code we could use in Javascript.

This code will result in an O(n) time complexity and would save use a good amount of computing time.