Week 3: Two Pointers

As its name suggests, in a two pointers style algorithm, we setup two different pointers at beginning. These two pointers can be opposite-direction or same-direction, and they may have different speed, i.e. slow and fast pointers. Two pointers tends to have worse time complexity but O(1) space complexity. If a follow-up question asks you to solve “in-place”, that is, with $latex O(1) space complexity, you should keep two pointers in mind.

1. Opposite-direction Two Pointers:

A very simple example is to reverse a list:

# suppose s is a list of characters
def reverse(s):
    start, end = 0, len(s) - 1
    while start < end:
        s[start], s[end] = s[start], s[end]
        start += 1
        end -= 1

Here, start and end are two pointers, and they move toward each other in the list. That’s why it is called “opposite-direction”. Another example is to determine if a string is palindrome, without using the slice operator:

def is_palindrome(s):
    start, end = 0, len(s) - 1
    while start < end:
        if s[start] != s[end]:
            return False
        start += 1
        end -= 1
    return True

One famous question regarding opposite-direction two pointers is Two Sum:

LeetCode #1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9, 

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Using Hash Table (O(n) time and O(n) space):

This question has a very elegant solution, which uses a set to track all numbers that we have seen:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = set()

        for i in range(len(nums)):
            if target - nums[i] in seen:
                return [nums.index(target-nums[i]), i]
            else:
                seen.add(nums[i])

The time complexity is O(n) since we use a hashmap. The space complexity is also O(n), for constructing the set. Here comes a follow-up question: what if we are required to write an O(1) space complexity algorithm? Now we need to use two pointers. The algorithm is the following:

Using Two Pointers (O(n\log n) time and O(1) space):

  1. Sort nums.
  2. Create two pointers representing an index at 0 and an index at len(nums) - 1.
  3. Sum the elements at the pointers.
    • If they produce the desired sum, return the pointer indices.
    • Otherwise, if the sum is less than the target, increment the left pointer
    • Otherwise, decrement the right pointer.
  4. Go back to step 3 unless the pointers are pointing to the same element, in which case return failure.

2. Same-direction Two Pointers:

Let’s start with a “slow and fast pointers” question:

LeetCode #26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.Using Hash Table:

Solution:

Since we are required to build an in-place solution, we can’t simply use a set to do this job. Two pointers is suitable in such scenario. The algorithm can be summarized as these steps:

  1. Initialize a pointer i to index 0.
  2. Initialize a pointer j to loop through the array starting from the second element.
  3. Compare the elements pointed by i and j: if they are equal, which means there is a pair of duplicate, just skip it; if they are not equal, let i points to the next element, and then update the element at index i to the element at index j. Note that at this point, the index i had already been incremented.
  4. At the end, the slice from nums[0] to nums[i] is an array with all duplicates removed. We simply return the length of this slice, which is i + 1.

If you are still confused about the updating procedure, you can look at a test case, for example, [0, 0, 1, 1, 1, 2, 2, 3], and follow above algorithm manually. Here is the code:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
            
        i = 0
        
        for j in range(1, len(nums)):
            if (nums[j] != nums[i]):
                i += 1
                nums[i] = nums[j]
        
        return i + 1

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 )

Google photo

You are commenting using your Google 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