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 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**:

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 ( time and 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 since we use a hashmap. The space complexity is also , for constructing the set. Here comes a follow-up question: what if we are required to write an space complexity algorithm? Now we need to use two pointers. The algorithm is the following:

**Using Two Pointers ( time and space):**

- Sort
`nums`

. - Create two pointers representing an index at 0 and an index at
`len(nums) - 1`

. - 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.

- 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:**

Givennums=[1,1,2], Your function should return length =, with the first two elements of`2`

being`nums`

and`1`

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

**Example 2:**

Givennums=[0,0,1,1,1,2,2,3,3,4], Your function should return length =, with the first five elements of`5`

being modified to`nums`

,`0`

,`1`

,`2`

, and`3`

respectively. It doesn't matter what values are set beyond the returned length.`4`

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:

- Initialize a pointer to index 0.
- Initialize a pointer to loop through the array starting from the second element.
- Compare the elements pointed by and : if they are equal, which means there is a pair of duplicate, just skip it; if they are not equal, let points to the next element, and then update the element at index to the element at index . Note that at this point, the index had already been incremented.
- 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 .

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