This week, I learned more about the Two Pointers coding pattern.

I came across this pattern when I was already looking at the problems tagged under Sliding Widow, which I focused on in another blog post. That’s when I decided to take a look at Two Sum and Contains Duplicate II. These are both considered easy problems, they’re really similar, and you’ll probably see why.

According to Kushleen Waraich from codingninjas.com, this is a coding pattern in which two pointers iterate over a data structure until one or both of them meet a certain condition. Kushleen says that a pointer is a reference to an object, storing a memory address of a particular value in computer memory. Kushleen also says to simplify the concept, a variable storing the address to an array is a pointer, and we can leverage that to solve these kinds of problems.

According to algodaily.com, this type of technique is commonly used for arrays, strings, or lists, where you need to analyze an element and compare it to other elements in the data structure. Algodaily.com’s author states that the two pointer technique is a much more space and time efficient way to process a loop because two elements are processed at a time.

According to algodaily.com, this technique is usually in one of the following two forms, “1. Two pointers, each starting from the beginning and the end until they both meet 2. One pointer moving at a slow pace, while the other pointer moves at twice the speed” (algodaily.com).

Given that information, let’s take a look at these problems and think about how to apply this kind of strategy.

The first problem is called Two Sum, and this is a really popular coding interview question that you may or may not already heard of. Here is the problem from the leetcode.com website:

https://leetcode.com/problems/two-sum/

According to the leetcode website, the prompt for Two Sum is as follows:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

The examples from the prompt on leetcode are as follows:

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

What would an approach be? Well, without really considering any data structures or fancy stuff, we could use a brute force type of method. If we wanted to use a brute force kind of approach, we could iterate over the array element by element, and check the other numbers against our current element to see if we have a match for the target at the two indices. It would be fine and get the job done for a very short input of data. For a longer input of data, not so much. This wouldn’t be the most optimal or efficient solution.

The next question to consider is, how can we calculate the pairs of values that add up to the target? We have a target value, minus a current value to get the complementary value with subtraction, or we could access the values by their index and check if the sum of the two is equal to the target value.

But we have to iterate in two places, and the reason is because the prompt specifies ‘you may not use the same element twice’, so you need your pointers to be pointing to two distinct elements at the same time. You could use pointers to iterate in any direction you’d like, but you’d want to cover all the elements, so one way to accomplish that is probably to start from the beginning and start at the end.

Another way to do a problem with two pointers, is using Hash Maps. According to geeksforgeeks.com, this is a data structure that allows efficient lookups and uses mapping of key and value pairs into different buckets, similar to a cabinet with different drawers for storing items.

If we wanted to solve this problem, we’d want to initialize the empty hash map so we have a place to store our data for the problem. Then we’d want to iterate over the original array with our two pointers, and try to find our needed condition. If we’re using Python, we can use the Python built-in dictionary as our hash map.

If we want our result to be even more optimized, we could make our approach even more efficient if we add the minimum amount of values to the hash map to achieve the goal. So before adding a key/value pair to the hash map, we could check if one is already present that if added to the current value, would equal to the target value. That’s when we would meet our condition.

Another way we could think about this is, when subtracting the current value from the target value, is the complimentary value that would achieve the target sum already in the hash map? If so, we found the answer, without having to necessarily create a hash map for the full array. That’s more efficient as long as one or two of the complementary pairs are not located at the end of the array. If these values aren’t at the end of the array, then we could have a pretty optimal solution.

So we could determine what is our current value, and what is the complimentary value needed to achieve the target sum. Then we could determine is the complimentary value already in the hash map, if so, we have the answer and we can return it. Otherwise, we could keep adding to the hash map, and continue iterating over our array.

In my solution, I initialized an empty dictionary, and then iterated over the array. I determine what is my complimentary value that I need to find in the dictionary, and is it already in the dictionary. If so, there’s the pair and I’m done. If not, I want to build my dictionary with key and value pairs, so I build it by putting the element of the list as a key, and its position in the list as the value. I take advantage of a python method called .get() which works with python dictionaries, where given a key, will return the corresponding value. If it can’t find the key in the dictionary, this particular method will instead return None. I keep building my dictionary with elements and their positions in the array, until I find my answer and return it. In the prompt, we have a guaranteed answer, so we don’t have to worry about what would happen if we can’t find the pair or exhaust the array.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        hash_table = {}
        
        for num in range(len(nums)):
            compliment_value = target - nums[num]
            if hash_table.get(compliment_value) != None:
                return hash_table[compliment_value], num
            else:
                hash_table[nums[num]] = num

Contains Duplicate II has a somewhat similar kind of idea. Here is the problem:

https://leetcode.com/problems/contains-duplicate-ii/

From the leetcode website, here is the prompt and the provided examples:

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i – j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

For this solution, the idea is really similar, you have two values in an array which may or may not be equal when doing a comparison at their indexes, but they must not be more than a specified distance apart from each other in the array.

In other words, you can use a hash map to store these numbers and their respective positions in the array, and quickly perform lookups to see if you get the target condition. In this case, the problem asks for a True or False result to be returned.

We can iterate over the array of numbers, and store the number and it’s position as key and value pairs in a python dictionary. If the dictionary already contains the number we’re looking for, then we know we have a duplicate number in the original array, and that’s when we would want to perform the calculation. Otherwise, we want to continue to add key/value pairs into the dictionary until we exhaust the whole list, because there is not a guaranteed solution for this problem.

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        
        hash_table = {}
        
        for num in range(len(nums)):
            index = num
            value = nums[index]
            if hash_table.get(value) != None:
                if abs(hash_table[value] - index) <= k:
                    return True
            hash_table[value] = index
        return False

Sources:

AlgoDaily. “Daily Coding Interview Questions. Full Programming Interview Prep Course and Software Career Coaching.” AlgoDaily, https://algodaily.com/lessons/using-the-two-pointer-technique. Accessed 13 Oct. 2022.

“Hash Map in Python.” GeeksforGeeks, 9 May 2022, https://www.geeksforgeeks.org/hash-map-in-python/. Accessed 13 Oct. 2022.

Waraich, Kushleen. Code Studio, https://www.codingninjas.com/codestudio/library/what-is-a-two-pointer-technique. Accessed 13 Oct. 2022.