Two pointers problems are commonly easy and medium questions in Leetcode,, and may become difficult questions under specific question backgrounds and requirements.
If it is a sliding window, the difficulty is basically in the medium and difficult level.
Overview
Two pointer is the first intermediate algorithm that most algorithm beginners can come up with individually on their way to advanced level.
When faced with a local search problem in an array (i.e. finding a segment that meets the conditions of arr[i:j]). Compared with O(N^2) brute force cracking, under certain requirements, algorithm beginners will start to think: Is there a way to solve the problem by searching the array only once?
After some hearty thinking, the beginner will realize that Compared with the mindless movement of the two search pointers i and j by brute force, it is entirely possible to record more meaningful content by customizing the movement rules of the pointers, thereby ignoring some unnecessary repeated searches and achieving O(N) time complexity.
It is also at this time that most beginners begin to realize the meaning of exchanging space (complexity) for time (complexity).
Of course, double pointer is a very general and rough name. Any algorithm that uses two pointers with specific movement rules can be called double pointer. Therefore, the binary search method can also be regarded as a double-pointer algorithm, but the essence of the binary search algorithm still lies in the core idea of binary search.
Categories of Two Pointers
We can categorize the Two Pointers into four main categories based on the moving pattern of the two pointers.
- Left & Right / Head & Tail / Collision Feature: One array, move from two sides to the middle / towards each other
- Fast & Slow (Forward) Feature: One array, both move forward/the same direction, in different pattern
- Parallel
- Sliding Window Feature: Both pointers moving in the same direction at a fixed difference of k.
Usually used in: search in ordered array (binary search)
Usually used in: Linked List, search for cycle / middle point
Usually used in: Searching in more than one array & Merging two sorted sub-arraies in Merge Sort.
Usually used in: subarray, string, substring
Difficulty in Two Pointers⭐️
There are generally only two difficulties, corresponding to design and implementation:
- Design: Is it possible to clearly define the movement strategies of the two pointers (what are the two pointers used for?)
- Implementation: Can you take all edge cases into account during coding (can you write them down or not)?
Usually it is because of lack of sufficient practice that one does not think of using the two-pointer algorithm [which is the most inappropriate thing], or one cannot figure out the movement logic of the two pointers, resulting in failure in solving the problem. Therefore, for Difficulty 1, there is no other technique except practicing more.
Difficulty 2The other problem is that you lack sufficient coding skills and lose patience or make mistakes when dealing with complex logic. Unlike Difficulty 1, this problem can be solved with some skills.
Trick:「Loop Invariant」
The loop invariant refers to an unchanging property that we must follow when writing code.This property requires us to define it according to the problem, It is important to ensure that the three stages of 「initialization」, 「loop traversal」 and 「ending」 have the same properties so that a problem can be solved correctly.
Different definitions of intervals determine different initialization logic and logic during the traversal process.
Therefore, the loop invariant is not the essence of the so-called two-pointer algorithm, but a technique to write a two-pointer solution sufficiently thorough for complex problems.
This trick can also apply to other algorithms.Problem Collection of Classic Two Pointers
| ID | Problem | Diff | Two Pointers Solution |
|---|---|---|---|
| 26 | Remove Duplicates from Sorted Array | Easy |
Type: Fast & Slow Fast pointer: Keep searching for next unknown element. |
| 674 | Longest Continuous Increasing Subsequence | Easy |
Type: Fast & Slow Fast pointer: Keep searching for the next element that satisfies the monotonically increasing When the fast pointer element violates monotonically increasing, the slow pointer moves to the position of the current fast pointer, which means searching for a new increasing sequence. |
| 977 | Squares of a Sorted Array | Easy |
Type: Collision Left pointer: Indicates that the negative end may compete for the element with the maximum value after square Hint: When negative and positive numbers can be excluded, the result can be directly output |
| 27 | Remove Element | Easy |
Type: Fast & Slow Fast pointer: Constantly looking for the next element that does not need to be removed |
| 80 | Remove Duplicates from Sorted Array II | Medium |
Type: Fast & Slow Fast pointer: Continuously searches for the next element and decides whether to insert and update the reference element based on the number of repetitions. |
| 283 | Move Zeroes | Easy |
Type: Fast & Slow Fast pointer: Keep looking for the next non-zero element |
| 11 | Container With Most Water | Medium |
Type: Collision Left pointer: Points to the left border of the current traversal layer |
Problem Collection of Tricky Loop Invariant Two Pointers
| ID | Problem | Diff | Two Pointers Solution |
|---|---|---|---|
| 75 | Sort Colors | Medium |
【Dutch National Flag Problem⭐️】 Type: Collision [variant]
Fast pointer: Locate the position to swap 1 There exists a situation where both right pointer and i are 2, so we need to use "while i <= right and nums[i] == 2: … right -= 1" to make sure that we won't miss the 2 on the left [if we takes the index from 0 to n-1 by default] |
| 215 | Kth Largest Element in an Array | Medium |
[A variant of Quick Sort] Type: Collision [variant] The left and right pointers are not prestigiously distinguished, with the Sentinel Division and Recursion to partition the left & right of the pivot, till the end. Trick: Quick SelectionThe question requires finding the Kth largest value, so there is no need to sort the array. Instead, it is similar to a binary search. When the number on the left and right sides of the pivot can determine that the Kth largest value does not exist in an interval, the interval can be discarded directly. Because the time complexity is required to be O(N), it is obviously a divide-and-conquer algorithm. |
| 59 | Spiral Matrix II | Medium |
【Simulation Method based on Loop Invariant】 Loop Invariant: Simulated by layer, and there are 4 edges in each layer, can be represented by the intervals:[left,right), [up, down),[right, left), [down, up). Till all the layers are traversed. |
Problem Collection of Two Pointers in Linked List
| ID | Problem | Diff | Two Pointer Solution |
|---|---|---|---|
| 141 | Linked List Cycle | Easy |
Type: Fast & Slow Fast pointer: traverse 2 nodes each step. |
| 19 | Remove Nth Node From End of List | Medium |
Type: Fast & Slow Fast pointer: N nodes ahead of slow pointer. If the fast pointer has reached the end, then directly remove the next node at the slow pointer. |
| 876 | Middle of the Linked List | Easy |
Type: Fast & Slow Fast pointer: traverse 2 nodes at a time. |
| 142 | Linked List Cycle II | Medium |
Type: Fast & Slow Fast pointer: traverse 2 nodes at a time. Might need some mathematical mindset Assume there are a nodes before the entrance of cycle, and there are b nodes in cycle, you will notice: Once the two pointers meet, the fast pointer mvoe twice the nodes than slow pointer, so we can have:
Substract x from 2x, and we can prove that
Now we need to reconstruct the Fast & Slow pointers, and the slow pointer can point back to head, and the two pointers now need to walk in the same pace, so they will meet at the entrance of the cycle. |
| 160 | Intersection of Two Linked Lists | Easy |
[This question does not require space complexity, and can be solved with a hash table, so it is a simple question,
but the double pointer can be O(1) space, O(m+n) time, this step is a little difficult,
it is considered medium difficulty] Type: Two Single Pointers Trick: the core technique is actually to align the two linked lists. You can find the length by traversing, and then align the two according to the length, and then traverse both linked lists synchronously from the beginning with a pointer. When you traverse to the same node, it is the intersection entrance. |
Problem Collection of Two Pointers Improving Deduplication
This type of problem usually has one or more typical solutions, but the algorithm that simplifies the retrieving process often makes the deduplication process more complicated. The deduplication complexity can be simplified by using sorted double pointers.
| ID | Problem | Diff | Two Pointer Solution |
|---|---|---|---|
| 15 | 3Sum | Medium |
【Hash Map Solution】
On the basis of two sum, the most typical solution would be Hash Map, which only takes two nested for loop to determine the value of a + b. And then determine wheter 0-(a+b) exists in the array using HashMap. This idea is actually correct. However, the major issue is deduplication, as the question suggests that the return array should not contain any duplicated combination. It is very time-consuming to first find all the unique triples in the index through hashing and then remove them, which may easily time out. It would be more efficient to solve this problem by using two pointers than hashmapsDue to the complexity of this problem, the double pointer type we are going to use is also quite special, which I call: Nested Collision Pointers First we need to sort the array, and has a for loop, where i starts from index 0, and init a pointer left starting at index i+1, along with another pointer right starting at the end of the array. Pointers Startegyif nums[i] + nums[left] + nums[right] > 0, then it means that the three sum is too large, and as the array has been sorted, so the right pointer needs to be moves to its left if nums[i] + nums[left] + nums[right] < 0, then it means that the three sum is too small, so left needs to go right, until left and right eventually meet. |
| 18 | 4Sum | Medium |
The same idea with 15. 3Sum. Using Two Pointers, and only requires one more for loop nested on the basis of 3Sum. The solution is to have two nested for loop, where nums[k] + nums[i] are certain, and still have left and right pointers within each for loop, and move based on the three situations of: nums[k] + nums[i] + nums[left] + nums[right] == target, The time complexsity of 3Sum is O(n^2), where the time complexsity of 4Sum is O(n^3) 。 Likewise, 5Sum, 6Sum, etc can be solved in similar manners. |
Think: Can we simplifies the Two Sum problem using Two Pointers?
The answer is NO. It is very simple, because the Two Sum problem needs us to return index, instead of values, so we cannot sort the array.
Note: You can get more Two Pointers exercises through the [Similar Questions] function of Leetcode