Two is Better Than One

The Two Pointer Pattern

This will be the first post in a series where I will cover common coding patterns used for solving LeetCode and whiteboard questions. These types of questions can be challenging even for the most seasoned developer. However, by knowing common patterns that can be utilized when solving these problems, you’ll go from zero to hired in no time.

This pattern involves two pointers (or references) used in order to more efficiently iterate through a data set. The pointers will work together to iterate through the data until a predefined target condition is reached. The data set is often a standard array (strings and linked lists are also applicable). It’s very suitable when asked to identify certain patterns in the data, such as:

  • Are there duplicate entries in the array?
  • Given a string, return the string in reverse
  • Are there two elements in the array that sum to a target value? This is most famously known as the Two Sum problem.

Generally speaking, you’ll know to use some form of this technique when any of the following are true:

  • The data is already sorted or you’re allowed to sort the data and having it sorted can be beneficial to your solution
  • The solution is expected to return a pair/triplet of elements or even a subarray of the original array

However, the major advantage that the two pointer pattern provides is in terms of time and space complexity. A solution that utilizes this pattern will usually lead to a time complexity of O(n) and space complexity of O(1). This is a huge win compared to alternative, brute force solutions that provide time complexities of O(n2) and space complexities of O(n).

The Two Sum Problem

Hopefully by this point, I’ve convinced you of the importance and power behind the two pointer pattern. However, to better frame these advantages, we’ll use a very common whiteboard question, which is the aforementioned Two Sum problem:

Given an array nums and an integer target, find two indices within nums whose elements sum up to target. You may assume that each input will have a unique solution and you cannot use the same element twice. For example:

nums = [1, 2, 3, 4, 5]

target = 5

output = [0, 3]

Let’s solve this problem first using a brute force approach and then the two pointers pattern to highlight its advantages. All code samples are written in Kotlin.

Brute Forcing the Sums

Any developer, whether a recently hired junior or a seasoned senior, would likely fall back to the brute force approach if they didn’t know about two pointers (or any other patterns). With the pressure and heat of the interview steadily rising and your time dwindling away, you’ll have no choice but to resort to using brute force to have some sort of solution:

fun twoSumBruteForce(data: IntArray, target: Int): IntArray {
    for ((firstIndex, firstNumber) in data.withIndex()) {
        for ((secondIndex, secondNumber) in data.withIndex()) {
            // Skip any duplicate entries
            if (firstIndex == secondIndex) {
                continue
            } else if ((firstNumber + secondNumber) == target) {
                return intArrayOf(firstIndex, secondIndex)
            }
        }
    }

    return intArrayOf()
}

Kotlin Playground

This solution does work, but there are certainly several drawbacks:

  • The nested for-loops are indicative that the time-complexity is indeed O(n2)
  • Related to the previous point, this solution does not scale. As the input size increases, the amount of time to process the data will increase exponentially

Space complexity isn’t compromised, which at least is a benefit. But there must be a better solution 🤔

Two Pointer Teamwork to the Rescue

As you likely have guessed, we can reduce our time complexity for this problem if we utilize the two pointer technique. First, we’ll have to sort the array (most languages and/or frameworks provide this out of the box). Next, we’ll create our two pointers. The first, called low, will refer to the first element of the array. The other pointer, called high, will refer to the last element. Before diving into the code, let’s take a look at what this gives us with all of these tools on hand (sorted array with two pointers):

Sorted array with initial low and high pointers

It may not be immediately obvious what these tools provide us. However, as a starting point, one thing we can do is sum up the elements that low and high are pointing to, which gives us 6. Another thing that we know is that in their initial state, low points to the lowest value in the array and vice versa for high. Now let’s recap what we know so far:

  • The input array has been sorted
  • The two elements that low and high refer to sum to a value greater than our target of 5
  • low and high point to the lowest and greatest values in the array, respectively

Therefore, we can conclude that we need to find a pair of elements that sum to a value less than the sum we’ve found so far. How can we find such a sum, using just the pointers we have? One option is to move low one element to the right while keeping high in its current position:

Moving low one element to the right

Summing up the elements of low and high gives us… 7 🤔 Upon further inspection, you’ll notice that moving low across the array will give us higher and higher sum values. And this is exactly what we expect since the array has already been sorted. If we know that, then the opposite should be true if we move high one element to the left:

Moving high one element to the left

Eureka! That gives us the target that we’re looking for. This means that we can adjust high and low as we determine candidate indices for our answer. Our constraints will be:

  • If the sum is less than the target value, move low one element to the right: this will provide the next highest candidate sum
  • If the sum is greater than the target, move high one element to the left: this will provide the next lowest candidate sum

All that’s left is to throw this logic into some sort of a loop so that we can iterate over the array. We will likely want to continue making comparisons between low and high until they’re equal since we can’t use the same element twice in our output. With all of this in mind, let’s code up this bad boy:

fun twoSumTwoPointers(data: IntArray, target: Int): IntArray {
    var low = 0
    var high = data.size - 1

    while (low < high) {
        val candidateSum = data[low] + data[high]
        if (candidateSum == target) {
            return intArrayOf(low, high)
        } else if (candidateSum < target) {
            low++
        } else {
            high--
        }
    }

    return intArrayOf()
}

Koltin playground

The advantages of this approach should be quite clear. In terms of space complexity, it remains O(1), same as our brute force solution. However, the real advantage this has is in terms of time complexity. As we move the low and high pointers, they will only iterate through the array for a maximum of n times (the while() terminates once the pointers are equal). This algorithm will iterate n-times if:

  • high remains in place and low continuously moves to the right or
  • low remains in place and high continuously moves to the left or
  • the sum does not exist and low and high both gradually move to the center

Therefore, we can conclude that the time complexity is simply O(n), which is a huge win over the O(n2) brute force approach.

Two Pointers for the Win

In this first post, I hope that I’ve gotten you excited and motivated to start using the two pointer pattern. It’s a technique that I’ve seen used very frequently in whiteboard-like questions and can be used to solve some intricate, complex problems. Stay tuned for my next coding pattern post. In the mean time, go score some two pointers:

Happy coding everyone!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s