Today, we’ll dive into a powerful problem-solving technique often used in array and string challenges: the Two Pointers method.

This approach is particularly effective for its simplicity and efficiency, allowing us to traverse iterables with minimal overhead and optimal performance.

Understanding Two Pointers

The Two Pointers technique, as the name suggests, involves two indices, typically referred to as left and right, which navigate through an array or string. This method is versatile, with various implementations depending on the specific problem at hand.

A common strategy starts with positioning left at the beginning and right at the end of the iterable, gradually moving them towards each other. This approach is particularly useful for problems that require examining elements from opposite ends and moving inward.

Consider the following steps to employ this strategy:

Initialize left at the starting index (0) and right at the last index (length - 1). Loop with a while condition where left < right, ensuring the pointers meet or cross. Inside the loop, perform necessary checks or operations and then decide whether to increment left, decrement right, or both, based on the problem’s requirements.

Here’s a simple illustration in pseudocode:

    void twoPointersTechnique(int[] array) {
        int left = 0;
        int right = array.length - 1;
        
        while (left < right) {
        // Perform necessary operations and checks
                
        // Update pointers as needed
           left++;
           right--;
        }
    }

The power of this technique is that never have more than O(n) iterations for the while loop, because the pointers start n away from each other and move at least one step closer in every iteration. Therefore, if we can keep the work inside each iteration at O(1), this technique will result in a linear runtime, which is usually the best possible runtime. Now, let’s proceed to explore some practical applications of this approach.

Practical Examples

Example 1: Palindrome Check

A classic application of the Two Pointers method is in checking whether a given string is a palindrome. This involves comparing characters from both ends of the string, moving inward.

Given a string str, return true if it is a palindrome, false otherwise. A string is a palindrome if it reads the same forward as backward. That means, after reversing it, it is still the same string. For example: “abcdcba”, or “racecar”.

Reversing a string swaps its first and last characters. For a palindrome, this means each character matches its counterpart from the end. Using a two-pointer approach allows us to compare these matching pairs. Starting at the ends, we move the pointers inward after each comparison, continuing until they meet or a mismatch is found.

    public boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
    
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

Notice, even if we switch from a string to a character array, our algorithm’s core approach, the two-pointers technique, remains effective. It’s adaptable to any linear structure by simply adjusting index movements.

This method stands out for its O(n) time efficiency and minimal O(1) space usage, requiring only two integer variables regardless of input size. Its linear time complexity is due to the pointers, starting n steps apart, moving one step closer each iteration, ensuring no more than O(n) iterations.

Example 2: Two-Sum in a Sorted Array

Given a sorted array and a target sum, determine if any two numbers in the array add up to the target. return true if there exists a pair of numbers that sum to target, false otherwise. For example, given nums = [1, 2, 4, 6, 8, 9, 14, 15] and target = 13, return true because 4 + 9 = 13.

In the brute force approach, we’d comb through every possible pair in the array, a method that quickly balloons to O(n²) time complexity for an array of size ‘n’. Yet, given our array is sorted, the two pointers method offers a sleek O(n) solution.

Take the sorted array [1, 2, 4, 6, 8, 9, 14, 15] with a target sum of 13. Starting at the ends, we sum the first and last elements, getting 16. Since this is over our target, we inch the right pointer left to decrease the sum. We continue adjusting our pointers inward based on whether the current sum is above or below the target, until we land on the pair 4 and 9, which hits our target sum.

The sorted array is key here. Moving the left pointer right increases the sum, and moving the right pointer left decreases it. If the sum is too high, it’s clear we won’t find a solution with the current right element, so we move the pointer left. If it’s too low, we move the left pointer right. This ensures we only need a linear pass through the array, maintaining the O(n) efficiency.

Here, we start with pointers at the extremities, adjusting them based on their sum compared to the target.

    public boolean findTwoSum(int[] nums, int target) {
        
        int left = 0;
        int right = nums.length - 1;
    
        while (left < right) {
    
            int sum = nums[left] + nums[right];
            
            if (sum == target) {
                return true;
    
            } else if (sum < target) {
                left++;
    
            } else {
                right--;
            }
        }
        return false;
    }

Like in the previous example, this algorithm uses O(1) space and has a time complexity of O(n).

Another way to use two pointers

Exploring another facet of the two-pointer strategy, we realize that the classic approach of initiating pointers at opposite ends and converging towards the center is merely one of its many applications. The elegance of algorithms lies in their conceptual fluidity; “two pointers” is not a rigid technique but a malleable concept adaptable to diverse scenarios. We now venture into an alternative implementation, particularly useful when dealing with pairs of iterables, such as two distinct arrays.

Move along both inputs simultaneously until all elements have been checked.

Converting this idea into instructions:

To apply this method, we start by setting up two pointers, one for each list or array we’re working with. Position both pointers at the beginning of their respective sequences. Then, we loop through using a while loop that keeps going until one of the pointers gets to the end of its list or array. Within each loop cycle, we’ll move the pointers forward. This could mean advancing just one pointer or both, depending on what we’re trying to find out or achieve with our problem. The choice of which pointer to move is key to solving the problem effectively.

Keep in mind that when our loop wraps up because one pointer has reached the end, the other pointer might not have gone through its entire list or array. If our task requires checking every single element, we might need to add a few more steps to go through the remaining elements of the other list or array that wasn’t fully traversed.

Here’s some pseudocode illustrating the concept:

    function fn(arr1, arr2):
        i = j = 0
        while i < arr1.length AND j < arr2.length:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
        1. i++
        2. j++
        3. Both i++ and j++
    
        Step 4: make sure both iterables are exhausted
        Note that only one of these loops would run
        while i < arr1.length:
        Do some logic here depending on the problem
        i++
    
        while j < arr2.length:
        Do some logic here depending on the problem
        j++

Just like the first approach we talked about, this strategy is pretty efficient, taking a straight-line, or linear, amount of time relative to the sizes of the two lists or arrays we’re dealing with. We describe this as O(n+m) time, where ‘n’ is the length of the first list or array and ‘m’ is the length of the second.

This efficiency comes from the fact that in each step of our loop, we’re guaranteed to move at least one pointer ahead. And since we can’t move the pointers more times than the total number of elements in both lists combined, we ensure we’re not doing any unnecessary extra work. Let’s look at some examples.

Example 3: Given two sorted integer arrays arr1 and arr2, return a new array that combines both of them and is also sorted.

A straightforward way to do this might be to just put all the numbers from both arrays together and then sort them. If the total number of elements from both arrays is ‘n’, sorting them would typically take O(n⋅logn) time. This method would make sense if the arrays weren’t already sorted. However, since both arr1 and arr2 are sorted, we can use a more efficient strategy with the two pointers technique, bringing our time down to a more manageable O(n).

Earlier, we talked about ‘n’ being the size of one array and ‘m’ the size of the other. But now, we’re just calling the total size of both arrays together ‘n’. This might seem a bit confusing, but in the world of big O notation, we’re allowed to choose how we name our variables. We could have stuck with ‘n’ and ‘m’, but since we’re merging the arrays, it makes sense to think of the total number of elements as one big ‘n’.

This doesn’t really change the essence of our time complexity calculations, it just simplifies how we talk about them, especially since the total size is what matters most here.

We can create the result list step by step. Begin with two pointers at the start of each list and compare their items. With every step, we look at 2 numbers. The smaller number should be added to the result list first, so we add it and then move that marker forward.

    public List<Integer> mergeArrays(int[] arr1, int[] arr2) {
        
        // result will store the merged list
        List<Integer> result = new ArrayList<>();
        int i = 0;
        int j = 0;
    
        // Loop through both arrays until one ends
        while (i < arr1.length && j < arr2.length) {
            // Add the smaller value to the result and move that pointer
            if (arr1[i] < arr2[j]) {
                result.add(arr1[i]);
                i++;
            } else {
                result.add(arr2[j]);
                j++;
            }
        }
    
        // If there are remaining elements in arr1, add them to the result
        while (i < arr1.length) {
            result.add(arr1[i]);
            i++;
        }
    
        // If there are remaining elements in arr2, add them to the result
        while (j < arr2.length) {
            result.add(arr2[j]);
            j++;
        }
    
        return result;
    }

Like in the previous two examples, this algorithm has a time complexity of O(n) and uses O(1) space.

Example 4: Is Subsequence? Given two strings word1 and word2, return true if word1 is a subsequence of word2, or false otherwise.

A subsequence in a string is like picking some letters from a word without jumbling their order. You can skip some letters if you want. For example, from the word “abcde”, if you pick out ‘a’, ‘c’, and ‘e’ in that order, you get “ace”, which is a subsequence. But if you pick ‘a’, ‘e’, and then ‘c’, making “aec”, it doesn’t work because you’ve mixed up their order.

In this task, we’re looking to see if the letters from one word, let’s call it “word1”, show up in the same sequence within another word, “word2”, even if there are other letters in between. For instance, “ace” fits into “abcde” because “abcde” has ‘a’, ‘c’, and ‘e’ in the same order. It’s okay if there are extra letters scattered between them.

We can approach this problem using two pointers, enabling us to efficiently navigate through the strings in a single pass. If we observe that the current character in word1 matches the corresponding character in word2, it indicates we’ve successfully located word1’s character, prompting us to advance to word1’s next character by moving its pointer forward. Regardless of whether there’s a match, we always increment word2’s pointer at each step, suggesting that this algorithm could also be structured with a for loop. word1 qualifies as a subsequence of word2 if we can locate all of word1’s characters within word2, which is confirmed when word1Pointer reaches the end of word1.

    class SubSequenceVerifier {
    
        public boolean isSubsequence(String word1, String word2) {
            int word1Index = 0;
            int word2Index = 0;
    
            while (word1Index < word1.length() && word2Index < word2.length()) {
                if (word1.charAt(word1Index) == word2.charAt(word2Index)) {
                    word1Index++;
                }
                word2Index++;
            }
            
            return word1Index == word1.length();
        }
    }

Just like all the prior examples, this solution uses O(1) space. The time complexity is linear with the lengths of word1 and word2.

Extending the Two Pointers Approach

The Two Pointers technique isn’t limited to arrays and strings; it’s a conceptual tool that can be adapted to various data structures and problems. For instance, it’s equally applicable in linked lists, dynamic arrays, and even when dealing with two separate sequences simultaneously. Two pointers just refers to using two integer variables to move along some iterables. The strategies we looked at in this article are the most common patterns, but always be on the lookout for a different way to approach a problem. There are even problems that make use of “three pointers”.

Conclusion

The Two Pointers technique is a testament to the elegance and power of simplicity in algorithm design. By effectively utilizing two indices to navigate through data structures, we can achieve optimal time complexity with minimal space overhead. Whether you’re tackling a palindrome check, searching for a pair with a specific sum, or facing any number of array and string manipulation challenges, the Two Pointers method offers a robust and efficient solution.

In our coding journey, such strategies not only enhances our problem-solving skills but also deepens our understanding of algorithmic efficiency and data structure manipulation. Keep exploring, and any consideration about the article you can let know in the comments.