Two-Pointer Technique Overview The two-pointer technique is an algorithm that uses two pointers to iterate through a data structure (like an array or linked list) until one or both pointers reach a certain condition. It's often used for searching pairs, sorting, or finding specific subsequences. Efficiency: Reduces time complexity, often from $O(N^2)$ to $O(N)$. Common Use Cases: Finding pairs in sorted arrays (sum, target). Reversing strings/arrays. Removing duplicates. Finding substrings/subsequences. Merging sorted arrays. Approach 1: Pointers Moving Towards Each Other Typically used with sorted arrays/lists to find pairs or elements satisfying a condition. General Structure int left = 0; int right = array.length - 1; while (left Example: Find Pair with Target Sum (Sorted Array) Given a sorted array and a target sum, find if any pair sums up to the target. public boolean findPairSum(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left Approach 2: Pointers Moving in the Same Direction Often used for problems involving subarrays, sliding windows, or modifying an array in-place. General Structure int slow = 0; for (int fast = 0; fast Example: Remove Duplicates from Sorted Array (In-place) Given a sorted array, remove duplicates in-place such that each unique element appears only once. Return the new length. public int removeDuplicates(int[] arr) { if (arr.length == 0) return 0; int slow = 0; // Pointer for the next unique element position for (int fast = 1; fast Example: Sliding Window (Fixed Size) Find the maximum sum of a subarray of size $k$. public int maxSubarraySum(int[] arr, int k) { if (arr.length Key Considerations Data Structure: Is it sorted? Can it be sorted? Pointer Initialization: Where do the pointers start? Movement Logic: How do pointers move? (e.g., $left++$, $right--$, $slow++$, $fast++$) Termination Condition: When does the loop stop? (e.g., $left Edge Cases: Empty array, single element array, $k=0$ or $k > N$. Common Patterns Palindrome Check: Pointers from start and end towards center. Reverse Array/String: Swap elements at pointers moving towards center. Partitioning: One pointer for current element, another for partition boundary. Interval Problems: Often involve sorting and then iterating with two pointers.
