# The Power of Two Pointers

Two pointer approach is extensively used since it provides \(\mathcal{O}(n)\) time and \(\mathcal{O}(1)\) space. It is especially tailored for linked list problems which often involves at least one pointer for linked list traversal. Fast-slow pointer pair is one representative instance of two pointer approach:

`141 Linked List Cycle`

If there is a cycle, then fast pointer with catch up with slow pointer. O(1) memory and O(n) time.

`142 Linked List Cycle II`

\(>141\) we need to locate where the cycle starts. After 2 pointers meet, reset one pointer and proceed 2 pointers both one step at a time until they meet again.

`876 Middle of the Linked List`

Return directly when fast pointer reaches the end.

`19 Remove Nth Node From End of List`

The fast node offset by N and then both proceed with the same speed

`160 Intersection of Two Linked Lists`

Brute force (\(\mathcal{O}(mn)\) time \(\mathcal{O}(1)\) space) or hash table approach (\(\mathcal{O}(m+n)\) time, \(\mathcal{O}(max(m,n))\)) space complexity approach are simple. With two pointer approach, we could get \(\mathcal{O}(m+n)\) time and \(\mathcal{O}(1)\) space: first reach the end of linked list A and form a cycle by connecting the tail of linked list A to head of B. Now it is reduced to problem

`142 Linked List Cycle II`

, remember to disconnect A tail and B head at the end.

For general linked list problems, often we need dummy/temp pointers besides the iterator pointer to avoid losing states during inplace modification. The usage of two pointer is explicit when two linked lists are involved.

`82 Remove Duplicates from Sorted List II`

Unlike

`83 Remove Duplicates from Sorted List`

, we need a dummy prev pointer to record the node before the repeating chain.

`21 Merge Two Sorted Lists`

Remember to consider the edge cases when one or both of the given linked lists are NULL, also need to record the head and keep it static while let the iterator pointer of the new list proceed.

`206 Reverse Linked List`

Need a dummy prev node pointed by curr.next during each iteration.

`92 Reverse Linked List II`

\(\approx 206\) with more temporary variables.

`25 Reverse Nodes in k-Group`

The problem is tagged as hard. The key is to modularize a helper API from

`206 Reverse Linked List`

which reverses a given linked list section (ListNode* reverse(ListNode* prev, ListNode* end)).

`24 Swap Nodes in Pairs`

Again, the key is to maintain a dummy prev node pointer for the pair to swap. For each swap, use tmp pointers to avoid losing states and then swap freely.

`61 Rotate List`

Equivalent to rotate by \(k\%n\)

`143 Reorder List`

Three steps: use fast-slow pointer pair to find the point to split, then reverse the second half, finally merge.

`86 Partition List`

Maintain 2 separate linked lists, and append to one of them during the iteration depending on the inequality before final concatenation.

`2 Add Two Numbers`

Straightforward since least significant number comes first.

Besides linked list, two pointer approach is also prevalent in problems over array-like data structures, often in the form of left and right pointer pair. Binary search is one concrete instance.

`704 Binary Search`

Basic binary search to find the index of target value. Use

`left + (right - left) / 2`

rather than`(left + right) / 2`

.`while`

condition and`left/right`

pointer update depend on whether the search set boundary is inclusive or exclusive (which is flexible).

`35 Search Insert Position`

Same as 704, but return left rather than -1 at the end

`34 Find First and Last Position of Element in Sorted Array`

When finding the first/last position of the target value, remember to check if the right/left boundary is exceeded*

`875 Koko Eating Bananas`

Optimize brute force search with binary search of first position of the value satisfying the constraint

`1011 Capacity To Ship Packages Within D Days`

Same as 875, but with different search boundary and helper constraint satisfying function

Sliding window approach is slightly more complicated and commonly used in substring problems. Unlike binary search, left/right pointer pair gets initialzied to the starting point, and the core loop is to iterate the right pointer.

`76 Minimum Window Substring`

Inside iteration: update metadata for the bigger window, shrink window by left pointer increment, check solution validity and update return. Hash map is needed as char counter (part of metadata) for this problem.

`438 Find All Anagrams in a String`

\(\approx 76\) except that the window length is fixed.

`3 Longest Substring Without Repeating Characters`

`567 Permutation in String`

\(\approx 76\) first find the shortest substring and return if no redundant chars. Or add an unmatch counter additionally to directly check the solution validity inside the left pointer loop.

There are other examples showing the usage of two pointer approach for arrays:

`167 Two Sum II - Input array is sorted`

Left pointer at start pointing and right pointer at the end.

`344 Reverse String`

Swap objects pointed by left/right pointer pair until they meet at the middle point.

`27 Remove Element`

Fast/slow pointer pair.

`26 Remove Duplicates from Sorted Array`

`80 Remove Duplicates from Sorted Array II`

\(\approx 26\) we allow up to 2 duplicates, hence an extra counter is needed.