Two Pointer Technique
Two-pointers is a really easy, effective, and efficient technique in data structures to search pairs in arrays or array-like data structures.
Types of Two Pointers Technique
Same Direction Pointers
Opposite Direction Pointer
Fast and Slow Pointer
Same Direction Pointer:
In the same direction approach, both pointers move through the array in the same direction, typically advancing by one or more positions in each iteration. The direction could be from left to right or right to left, depending on the problem. At each step or iteration, you check a certain condition involving the elements pointed to by the two pointers. This condition could involve comparing the values of the elements, checking for a certain pattern, or any other condition relevant to the problem.
Here are some practice problems for the same direction approach
https://leetcode.com/problems/minimum-size-subarray-sum/description/
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
Opposite Direction Pointer:
In the opposite direction pointers approach, you utilize two pointers that start at different positions in an array or sequence and move in opposite directions through the array until a certain condition is met. The time complexity of algorithms employing opposite direction pointers depends on the number of elements in the array or sequence and the condition being checked at each step. It's often efficient, especially for problems involving linear array traversal.
Here are some practice problems for the opposite-direction approach
https://leetcode.com/problems/two-sum/description/
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
https://leetcode.com/problems/3sum/description/
Fast and Slow Pointer
In the fast and slow pointers approach, you utilize two pointers that start at the same position in an array or sequence and move at different speeds through the sequence until a certain condition is met. The time complexity of algorithms utilizing fast and slow pointers depends on the number of elements in the sequence and the condition being checked at each step. It can often lead to efficient solutions, especially for problems involving linked lists, cycle detection, or finding middle elements.
Here are some practice problems for the opposite-direction approach
https://leetcode.com/problems/middle-of-the-linked-list/description/
https://leetcode.com/problems/linked-list-cycle/description/
https://leetcode.com/problems/linked-list-cycle-ii/description/
Complexity Analysis:
The time complexity of this solution would be O(N) because each element is at most visited twice. In the worst-case scenario, all elements will be visited once by the start pointer and another time by the end pointer. The space complexity would be O(1) because the solution doesn't create new data structures.