In today’s post, we will take a look at the two pointer pattern for solving problems. This pattern is really useful for traversing arrays, strings, and linked lists. The two pointer approach also encompasses binary search since these terms are really loosely defined. Let’s take a look at a set of problems that can be solved using this technique.

Problem #9 – Pair with Target Sum

This problem is fairly simple to think about. Given an array that is sorted, we need to find two numbers that add up to a target sum. This problem is actually the renowned 2-Sum LeetCode problem. It can be solved using a hash table as well, but since we are trying to learn the two pointer pattern, we will talk about that first and then solve it using a hash table.

Given that the array is sorted, we can initialize one pointer¹ at index 0, the start of the array, and the second pointer at the final element of the array. We’re guaranteed that an answer exists, so what we’re going to do is check if this combination equals the sum. If it’s lesser, then we will increment the low pointer. Otherwise, we’ll decrement the high pointer. It is guaranteed that this algorithm will converge to the right answer because the array is sorted. There’ll be a steady increasing or decreasing pattern followed until the answer is reached.

The time complexity of the solution is, worst case, O(N) if we need to iterate the entire list to find the answer. Space complexity for the solution is O(1), as no additional data structures are used.

Although this solution works, let’s discuss a clever usage of the hash table to solve this problem. This solution will work even if the array isn’t sorted, yet it is doable in O(N) time complexity, so it is interesting to understand how it works. Recall studying multi-variable algebra in school? Let’s use that stuff here. Imagine two variables being added together to a value, similar to the problem:

\[ x + y = 5 \]

If you are given x, how do you find y? Yes! y is simply going to be 5 – x. This is what we’re going to use to solve the problem using a hash table. We will start by iterating through the array. At each number, we will calculate the difference between the number and the target. We’re effectively calculating x or y; it doesn’t really matter which we calculate, all we’re doing is isolating one variable and looking for the other in the list. Then we’re going to check if a number in the has been added to the table already, and, finally, we will add the difference value as the key with the index value of the number as the value.

Let’s clarify using an example list = [1, 2, 3, 4, 5] and target = 6. As we begin looping through the numbers, we will start adding the numbers [5, 4, 3, 2, 1] to the dictionary alongside the index that let to us finding these differences i.e. the original numbers in the list. You can see that the solution to this problem has been essentially flipped when we do this! Part ur answer, [2, 4], will be found in the hash table as 4: 1, which is what we got after the 6 – 2 operation being saved at index 1.

The second part of this solution is to check during each iteration before adding new numbers to the dictionary if the current number is already in the dictionary or not. In the example above, we will already have the number 4 in our dictionary when we iterate over the element 2. Therefore, our condition will be true when we reach element 4 at index 3. So, at that point, we have found our answer to the question, which will just be the index of the current number being iterated on and the index of element 4 that we have saved to our dictionary, which really is the index to ‘2’ in reality.

This solution is O(N) time complexity in the worst case², although it will likely run in faster time on average. For space complexity, we will also have O(N), as we’re creating and building a hash table, which may have N elements in the worst case, when no combination of elements are found.

This is a really smart solution and takes some time to understand, so don’t worry if you cannot get it the first, second, or third time!

Problem #10 – Find Non-Duplicate Number Instances

This is a tricky problem that asks you to shift all non-duplicate numbers in a sorted list to the left and return the count of unique elements in the array. You are not allowed to use extra space, meaning no dictionaries, no extra arrays, no sets, nothing. You can solve the problem using two pointers, in a slightly different way than we’ve seen so far.

The way to efficiently solve the problem is to have one pointer iterate the array as usual. The trick is what the second point. It will be placed only on positions that can have the next available non-duplicate element. Given the array, [2, 3, 3, 3, 6, 9, 9], let’s visualize what we’re doing. There’s nothing to think about with respect to the first pointer, i. It will just go along the list as usual, visiting one element at a time. The second pointer, however, will be placed at position 1 in the very beginning³. By doing this, we will be able to check if the current element is different from the previous element. The array is sorted, so the moment we find a new element, we should place it into the next available non-duplicate slot and increment it.

Iteration #1: [2, 3, 3, 3, 6, 9, 9]; i = 0, non-duplicate = 1
Iteration #2: [2, 3, 3, 3, 6, 9, 9]; i = 1 non-duplicate = 1: check the item before ‘non-duplicate’. It is the first element 2, which is, of course, different from the current index, i = 1 = 3. Replace whatever is in array[non-duplicate] with array[i], which doesn’t change the array
Iteration #3: [2, 3, 3, 3, 6, 9, 9]; i = 2, non-duplicate = 2: no change
Iteration #4: [2, 3, 3, 3, 6, 9, 9]; i = 3, non-duplicate = 2: no change
Iteration #5: [2, 3, 6, 3, 6, 9, 9]; i = 4, non-duplicate = 2: the previous element is different from the current element (3 and 6), so set array[non-duplicate] to be 6 and increment it
Iteration #6: [2, 3, 6, 9, 6, 9, 9]; i = 5, non-duplicate = 3: (6 and 9) are different elements, so add 9 to index 3 and increment non-duplicate
Iteration #7: [2, 3, 6, 9, 6, 9, 9]; i = 6, non-duplicate = 4: 9 and 9 are equal and we’re done iterating the whole array!

Problem #11 – Squaring a Sorted Array

For this problem, we are given a sorted array, and we need to square all the elements and save them to a new array in sorted order as well. The tricky part here is that the numbers can be negative as well, and their squares will obviously become positive, so we need to account for that. We obviously have the brute force approach of creating a new array of squared numbers and then sorting them, with a time and space complexity of O(N + N log N), which will be O(N log N). But we can actually do better.

We will talk about two kinds of two pointer approaches that can solve this problem. One is significantly easier and takes less code, but we’ll still talk about the second one because it teaches us different ways of thinking and one important detail that I learnt while doing it this way.

First of all, let’s set two pointers to the start and end of the array. Since there are negative numbers involved as well, a big negative number could contribute a large value to our result. This means that we will have to build our result array backwards for this solution, so you will have to index into the array to set a number instead of appending it⁴. We build our array like so:

arr = [0 for _ in range(len(arr))]

# OR

arr = [0] * len(arr)

Now, we will start iterative both front and back, using our pointers, and comparing the squares that we find. We will add the greatest value from these two to the end of our array and shift whatever pointer we found the greatest value from either forwards or backwards. And that’s it! We should have a sorted squared array by the end.

The second solution is trickier. We will start iterating from the front and back from the mid point of the array. By doing so, we will not need to insert elements to our array from the back and can just append normally to the array. But this will bring a series of complications to the table. You need to find the first positive element in the array from where you can begin iteration, but there’ll be test cases comprising of entirely negative and positive numbers, so you will have to deal with that. Also, in the case of arrays with mixed numbers, there’s a chance that you will leave out some elements left on either end. Especially if you have a while that looks like so:

while positive_pointer < len(arr) and negative_pointer >= 0

The moment one condition is met, the loop exists so in the case of arrays like [-3, 0, 1, 2, 9] or [-8, -7, -6, 4], we could miss some key elements that could change our answer. So, after your main while loop, you will also need to make sure you have added all the elements on the left side and the right side of the array.

While coding this solution, I ran into a case which also showed me the importance of knowing the difference between checks such as if not variable and if variable is None, especially when dealing with numbers. In the case that I found a positive number at the very beginning of the list, I ended up with a variable, first_positive = 0. Further down the line, I check if this variable is None because that is how I initialized it; however, the way I checked it was “if not first_positive”. 0 is actually False in boolean, so the solution ended up assuming that I found no positive integers in the array, which is obviously not the case.

While in certain situations involving lists, dictionaries, strings, or booleans the “if not variable” is a perfectly fine way of checking if a variable is empty or False, when dealing with numbers, it may bring about unforeseen consequences such as it did with me in this problem. Lesson learnt: when dealing with integers, make sure to use explicit None checks like “if first_positive is None” or “if first_positive is False”.

Thus, for this solution, the way you use your two pointer pattern will change the nature of your solution, sometimes significantly. And if we want the smoothest interview experience, we must also think about how we are going to use the patterns, data structures, or algorithms that we identify.

Problem #12 – Triplet Sum to Zero

This is a great problem for a variety of reasons. There are multiple little things to keep in mind while doing the solution to pass all the test cases, so it refreshes many concepts. First of all, a brute force solution would work, but you would need three for loops leading to an O(N^3) time complexity, which is too slow for large inputs.

The optimal solution will be using the same concepts from the two sum problem. Our array is unsorted, so, first, we need to get that done. With that, we can have one variable that iterates the array and create two additional variables that scans the rest of the elements. We are breaking down the problem to these equations:

\[ x + y + z = 0 \]
\[ y + z = -x \]

x is going to be our iterating variable and we will start off pointer y at the x + 1th index, while pointer z will start at the end of the list. With this structure, we must also ensure that our iterating variable ends on the n – 2nd element, where n is the length of the array. This is so the last element that x can be will be the n – 3rd i.e. the third last element of the list, so we still have a y and z to calculate.

Once we have an x, we can start looking for two numbers that is going to equal -x; hence, our problem reduces to finding a pair with target sum, like Problem #9, within a sorted list. If we find a combination of y+z that is greater than -x, we reduce the right pointer⁵. In the case of a combination that is smaller, we increase the left pointer. Otherwise, we have found our triplet and it only took two loops!

There are additional considerations with this problem, however. Try implementing this solution and you will figure out really quick that there will be many repetitions in your solution: you will build a list filled with repeated triplets. Hence, we need to make sure to skip any x, y, z values that are the same as the previous value we have processed. Otherwise, we might end up with two lists like [1, 2, 4] and [1, 2, 4]. We don’t want that, so we will add some logic within the main iteration and the case where we find valid values for y and z.

This leads us to another technique that is frequently used and one you will need to think about more deeply in this problem than in others. When checking for duplicates in an array, there are two ways we can go about it. We can check the previous element or the next element. This is what this looks like in code.

# Checking the previous element

for i in range(1, len(arr):
    if arr[i] == arr[i - 1]:
        continue    # Or do other logic

# Checking the next element

for i in range(len(arr) - 1):
    if arr[i] == arr[i + 1]:
        continue    # Or do other logic

Notice how these methods subtly change the for loop because we need to ensure that our if statement logic does not cause an index out of bounds error. If we’re doing anything with the iterating variable, we need to ensure that we’re checking for worst case scenarios with that. Logically speaking, both of these ways of checking for duplicates are equivalent but they differ in one important way. Checking the previous element and skipping it means we still process one of the duplicated numbers. In this problem, we need to do that. There are other problems where we want to skip all cases of duplicated numbers. In that case, checking the next element makes sense, but in this case, we want to stick to checking the previous element like so array[i] == array[i – 1].

We’re also using the ‘continue’ keyword here because there may be many repetitions in the array, such as [2, 2, 2, 2, 3, 5]. We want to skip over all the twos once we process one of them. This is a matter of taste, as the same code could have been rephrased as

for i in range(1, len(arr):
    if arr[i] != arr[i - 1]:
        # Rest of the logic

As mentioned earlier, we also want to skip over duplicates of the other two numbers in the triplet. Where exactly do we do that? Well… once we find a valid pair that complements the first number x! We are using the two pointer pattern within our main loop and we have a binary search-esque if, else statements comparing the value of y + z (the pair we are trying to find) against -x (the first element found through the for loop). Again, we are shifting the values of our two pointers depending on if y + z is greater or smaller than -x. So, we take care of the duplicate logic when we find three valid triplets and add the values to our answer list. Subsequently, we will write some logic to skip over all duplications in y and z.

# Found three valid triplets
else:    
    answer.append([x, y, z])
    
    # Skip all repeated y's now
    while left < right and array[y] == array[y - 1]:
        y += 1

    while left < right and array[z] == array[z - 1]:
        z -= 1

Problem #13 – Triplet Sum Close to Target

This problem is a slight change to our prior problem. Here, we want to find triplets which are closest to our given target. Furthermore, we only want to return one answer: the closest triplet that is also the smallest. In the case that there are multiple such triplets (if 4 was the target, we could potentially have triplets equalling 2 or 6), we want to return the smallest one.

This problem, thus, removes the need to check for duplicates and skip over them. Now, the only thing left is to find the minimum smallest triplet, which can be done by calculating the absolute difference between the target and the calculated sum. We save the sum with the smallest absolute difference which basically means the sum value that is the closest to the target, in non nerd terms. But, here we add an additional check for the case where the current triplet sum is equal to the one we have found before. In this case, we check if the current sum is lesser than our result so far; if yes, then update our result to be the current sum. Et voila!

We can also solve the problem by using differences instead of the sum. We calculate differences from the target and the x, y, z triplet values we find. And we will try to minimize that because the smallest difference means the largest sum close to the target value. Here, in the case where we find two equal triplet sums, we will take the sum that results in a larger target difference, as that essentially means the smallest sum. Imagine having a target 4 but we end up with two triplets sums i.e. 2 and 6. The absolute differences we will have are 2 and -6, so we will pick the former value to get our answer, which is 2.

Remember to also talk about edge cases in interviews. In this problem (and the last), it is a good idea to check if the array if null or if the array has at least 3 elements. If you don’t want to do that, at least ask the interviewer if we can assume that the inputs provided will be valid and within boundaries.

We have more problems to solve to understand this technique, so stay tuned for another part of the two pointer pattern for solving LeetCode questions!

1. Fancy term for a variable ↩︎
2. Hash collisions are also something that could happen – which I will cover in a future blog post. In the case of really large inputs, these collisions may degrade our time complexity to O(N^2) ↩︎
3. There are two ways to check for duplicates in a sorted list. Either you can check the next element, by checking array[i] and array[i + 1] or you can check array[i] and array[i – 1]. Both have slightly different applications, and, for the former, you need to make sure to not overshoot and get an index-not-found error. Meaning, you must loop only till len(array) – 1. In this problem, we will be using the latter approach at it is more useful. ↩︎
4. Appending to arrays in Python can only be done forwards, so we cannot use this approach here ↩︎
5. Which will reduce y+z because the array is sorted ↩︎
6. Another important condition to remember! Without this, your two pointers might be made invalid. It isn’t enough that our two pointer while loop also has this condition. After all, our inner while loops may cause our pointers to cross the valid boundaries once it has cross the outer while loop. ↩︎