The two pointer technique is a near necessity in any software developer's toolkit, especially when it comes to technical interviews. In this guide, we'll cover the basics so that you know when and how to use this technique.
Using two pointers is exactly as it sounds: it's the use of two different pointers (usually in order to keep track of array or string indices) to solve a problem involving said indices.
The pattern can be used for string or array questions that can be streamlined and made more efficient by iterating through two parts of an object simultaneously, like in the Two Sum problem or Reverse a String.
One usage is while searching for pairs in an array. Let us consider a practical example: assume that you have a sorted array
The brute force solution is to compare each element with every other number, but that's a time complexity of
O(n^2). We can do better!
So let's optimize. You need to identify the indices
pointer_two whose values sum to integer
Let's initialize two variables,
pointer_two, and consider them as our two pointers.
pointer_one = 0 pointer_two = len(arr)-1
len(arr)-1 helps to get the last index possible in an array.
Also observe that when we start,
pointer_one points to the first element of the array, and
pointer_two points to the last element.
This won't always be the case with this technique (we'll explore the sliding window concept later, which uses two pointers but have them move in a different direction). For our current purposes, it is more efficient to start wide, and iteratively narrow in (particularly if the array is sorted).
def two_sum(arr, target): pointer_one = 0 pointer_two = input.length - 1 while pointer_one < pointer_two:
Since the array is already sorted, and we're looking to process an index at each iteration, we can use two pointers to process them faster. One pointer starts from the beginning of the array, and the other pointer begins from the end of the array, and then we add the values at these pointers.
Once we're set up, what we want to do is check if the current pointers already sum up to our target. This might happen if the correct ones are on the exact opposite ends of the array.
Here's what the check might look like:
if sum == targetValue: return true
However, it likely will not be the target immediately. Thus, we apply this logic: if the sum of the values is less than the target value, we increment the left pointer (move your left pointer
pointer_one one index rightwards).
And if the sum is higher than the target value, we decrement the right pointer (correct the position of your pointer
pointer_two if necessary).
elif sum < targetValue: pointer_one += 1 else: pointer_two -= 1
In other words, understand that if
target-arr[pointer_two], it means we should move forward on
pointer_one to get closer to where we want to be in magnitude.
This is what it looks like all put together:
def two_sum(arr, target): pointer_one = 0 pointer_two = input.length - 1 while pointer_one < pointer_two: sum = input[pointer_one] + input[pointer_two] if sum == targetValue: return true elif sum < targetValue: pointer_one += 1 else: pointer_two -= 1 return false
It's crucial to see that how both indices were moving in conjunction, and how they depend on each other.
We kept moving the pointers until we got the sum that matches the target value-- or until we reached the middle of the array, and no combinations were found.
The time complexity of this solution is
O(n) and space complexity is
O(1), a significant improvement over our first implementation!
Sign up for our newsletter list and join over 3,000 brilliant developers leveling up and solving coding challenges daily.