Two pointers is a powerful weapon of solving problems for data structures such as array and list. A classic example is to find out whether there is a cycle in a linked list.

I will collect some typical problems in this post and provide the solutions using two pointers.

## I. Fast Pointer & Slow Pointer

A fast pointer refers to a pointer that moves faster, like taking two steps at a time or taking a few steps ahead, and a slow pointer might take only one step at a time. A fast pointer and a slow pointer are often used to handle problems like a cycle in a linked list.

### i. A cycle in a linked list

141. Linked List Cycle: determine if there is a cycle in a linked list.

The idea is to let the slow pointer catch up the fast pointer. This will happen if the linked list contains a cycle.

### ii. Entry point of a cycle in a linked list

142. Linked List Cycle II: find out the node where the cycle begins in a linked list.

The key to the problem is that if it takes t steps for a slow pointer to walk from the first node to the entry node of the cycle, then the slow pointer can get to entry node starting from the meeting node in t steps, i.e. suppose r is the length of the cycle, m is the distance between the node where the cycle begins and the node where the fast pointer and slow pointer meet, and n is the distance between the first node in the linked list and the start node of the cycle, then we have

Note that k can be bigger than 1 if n is much larger than r.

How to prove this? Suppose it takes t steps for the slow pointer to meet the fast pointer for the first time, so we have

### iii. Duplicate number

287. Find the Duplicate Number: find the only one duplicate number in an array containing n + 1 integers where each integer is between 1 and n(inclusive).

The amazing thing about this problem is that it can be converted into the problem of a cycle in a linked list. Here is a thorough explanation on the trick. Simply speaking, the array contains n + 1 integers, so the range of its indices should be between 1 and n, which is exactly the same for each integer, and hence we can use the indices as the link to the next integer.

Here is an example.

index 0 1 2 3 4 5 6 7
number 7 2 3 1 6 2 4 5 The linked list starts from 0, because none of the integers can be 0 which makes sure we can build a linked list from it. Here is an example of why we cannot use other numbers as the start point.

index 0 1 2 3 4 5 6 7
number 7 1 2 3 4 5 6 7

Another solution is using binary search.

### iv. The Nth node

19. Remove Nth node: remove the Nth node from the end of a linked list.

The solution is to have the fast pointer take n steps ahead of the slow pointer, so when the fast pointer reaches the end of the linst, the slow pointer will be one step before the node being removed.

### v. Lowest Common Ancestor

Find the lowest common ancestor of two nodes in a binary tree, where each node has a link to its parent.

Actually this is a problem about finding the node at which the intersection of two linked lists begins.

1. Get the length of each list (from the specific node to the root)
2. Suppose the length of ListA is lenA and the length of ListB is lenB, and lenA is larger than lenB, put the fast pointer in ListA and take lenA - lenB steps ahead, and put the slow pointer in ListB
3. The LCA is the node at which the fast pointer and slow pointer first meet

## II. Sliding Window

The problems in this part can be solved by using a sliding window over an array or list. To represent a sliding window, we can use two pointers, one at the leftmost edge of the window, and the other at the rightmost edge.

### i. Substring

76. Minimum Window Substring: given a string S and a String T, find the minimum window in S which contains all the characters in T.

The idea is to have the sliding window move over the array and make sure that it covers all the required characters. The questions are how to move the left pointer and right pointer, and how to know if the window contains all the required characters.

Time complexity is O(t.len + s.len).

### ii. Subarray

209. Minimum Size Subarray Sum: given an array of n positive integers and a positive inter s, find the minimal length of a contiguous subarray of which the sum >= s.

For this problem, the sliding window is a contiguous subarray of which the sum is larger than s.

• Move the right pointer, until the sum of the window is larger than s
• Compare the window to the minimum size subarray
• Move the left pointer one step at a time

Time complexity: O(n).

### iii. Substring

567. Permutation in String: given two strings s1 and s2, check if s2 contains the permutation of s1.

It is similar to Problem i, the difference is that the sliding window can only contain characters of s2. Note that always move the right pointer first and then adjust the left pointer.

Time complexity: O(s1.len + s2.len * 2).

### iv. Substring

30. Substring with Concatenation of All Words: find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

It is similar to Problem iii, but instead of finding substrings that contain the required characters, it needs to find the substrings that contain the required words, so we need a way to verify if an index is a start index of a word. To solve this issue, we can build an index for each. Note that all the words are of the same length, so no word can be a prefix of other words.

Time complexity for this solution is: O(words.len + s.len * s.len).

### v. Substring

3. Longest Substring Without Repeating Characters: given a string, find the length of the longest substring without repeating characters.

The idea is that the sliding window should contain non-repeating characters, and the rest is the same as above.

## III. Others

### i. Two sum

167. Two Sum: given an array of integers which are in ascending order, return indicies of the numbers such that they add up to a specific target.

The idea is to have the left pointer move from the leftmost side and have the right pointer move from the rightmost side. Because the array is sorted, it is easy to decide whether to move the left pointer or the right pointer by comparing the sum to the target.

Time complexity: O(nums.len).