The two point method is commonly used with array problems. Lets take a beginner algorithm problem and see how we can use it:
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.
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.
This code will result in an O(n) time complexity and would save use a good amount of computing time.