Algorithms
Two Pointers Technique
Two indices walk through a structure — from opposite ends, same direction, or on separate sequences — reducing O(n²) brute force to O(n). The backbone of sorted-array pair problems, in-place partitioning, and linked-list cycle detection.
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation
What is Two Pointers?
Two pointers is a technique where two index variables traverse a data structure simultaneously — either moving toward each other from opposite ends, or moving in the same direction at different speeds. The key insight: by choosing which pointer to advance based on a comparison, you avoid examining every pair (O(n²)) and instead visit each element at most once or twice (O(n)). The technique requires some form of order or structure — typically a sorted array, a partitioned condition, or a linked list where relative position matters. Two pointers appears in four common patterns: (1) opposite-end convergence on a sorted array (Two Sum II, Container With Most Water), (2) same-direction read/write for in-place partitioning (Remove Duplicates, Move Zeroes), (3) fast/slow runners on linked lists (cycle detection, middle node), and (4) merging two sorted sequences. Each pattern is a different configuration of the same core idea: two indices, one movement rule, O(n) total.
Analogy: Two people searching a bookshelf from opposite ends. Person L starts at the left and steps right; person R starts at the right and steps left. They compare what they're holding: if the combined weight is too light, L steps right (to a heavier book); if too heavy, R steps left (to a lighter book). They meet in the middle having checked every possible lightest+heaviest pairing — without ever checking middle+middle or restarting from the beginning.
02
Section Two · Mental Model
How It Thinks
Array is sorted — increasing from left to right
▶
Moving the left pointer right INCREASES the sum of the two elements; moving the right pointer left DECREASES it — enabling directed search toward a target sum
Each step advances at least one pointer — either L++ or R-- (or both)
▶
At most n steps total before L and R meet — every element visited at most once — O(n) guaranteed
The "read" pointer scans ahead while the "write" pointer marks where to place the next valid element
▶
In-place partitioning: the read pointer finds valid elements, the write pointer compacts them — no extra array needed, O(1) space
Fast pointer moves 2 steps per iteration, slow pointer moves 1 step
▶
If a cycle exists, fast catches slow inside the cycle — like two runners on a circular track where the faster one always laps the slower one
Two sorted sequences each have a pointer starting at their beginning
▶
Compare the two pointed elements, take the smaller, advance that pointer — merges two sorted sequences in O(n+m)
Two pointers doesn't require sorted data for all patterns — partitioning and cycle detection work on unsorted data
▶
The common thread is not "sorted" but "each pointer moves in one direction only" — monotonic pointer movement guarantees termination and O(n) time
03
Section Three · Opposite Ends
Pattern 1 — Opposite-End Convergence
Start left pointer at index 0 and right pointer at index n-1. Compare, then advance the pointer that improves the result. The pointers converge toward each other, meeting in the middle. This only works when the array is sorted (or the problem has a similar monotonic property).
Two Sum II — Sorted Array (LC 167)
Find two numbers in a sorted array that sum to target. Return their 1-indexed positions.
Pseudocode
function twoSum(arr, target):
L = 0, R = arr.length - 1 while L < R:
sum = arr[L] + arr[R]
if sum == target:
return [L + 1, R + 1]
else if sum < target:
L = L + 1 // sum too small → need bigger else:
R = R - 1 // sum too big → need smaller return [-1, -1] // O(n)
Two Sum II — target = 10 on [1, 3, 5, 7, 9]
Container With Most Water (LC 11)
Given heights, find two lines that form a container holding the most water. Width = R - L, height = min(arr[L], arr[R]).
Pseudocode
function maxArea(heights):
L = 0, R = heights.length - 1
maxWater = 0 while L < R:
width = R - L
h = min(heights[L], heights[R])
maxWater = max(maxWater, width × h)
if heights[L] < heights[R]:
L = L + 1 // shorter side limits area → move it else:
R = R - 1 return maxWater // O(n)
Why move the shorter side?:
- The area is limited by the shorter line.
- Moving the taller line inward can only decrease width without increasing height — guaranteed worse.
- Moving the shorter line inward decreases width but might find a taller line — the only chance to improve.
04
Section Four · Same Direction
Pattern 2 — Read/Write (Same Direction)
Both pointers start at the beginning and move right. The "read" pointer (fast) scans every element. The "write" pointer (slow) marks the position where the next valid element should be placed. This pattern compacts an array in-place — removing duplicates, zeroes, or specific values without extra space.
Remove Duplicates from Sorted Array (LC 26)
Remove duplicates in-place from a sorted array. Return the count of unique elements.
Pseudocode
function removeDuplicates(arr):
if arr.length == 0: return 0
write = 1 // first element always unique for read = 1 to arr.length - 1:
if arr[read] != arr[read - 1]: // new unique element
arr[write] = arr[read]
write = write + 1 return write // O(n), O(1) space
Remove Duplicates — [1, 1, 2, 3, 3] → [1, 2, 3, _, _]
Move Zeroes (LC 283)
Move all zeroes to the end while maintaining the relative order of non-zero elements — in-place, O(1) space.
Pseudocode
function moveZeroes(arr):
write = 0 for read = 0 to arr.length - 1:
if arr[read] != 0:
arr[write] = arr[read]
write = write + 1 while write < arr.length: // fill remaining with zeroes
arr[write] = 0
write = write + 1 // O(n), O(1) space
The read/write pattern works for any filter condition:
- Remove duplicates (
arr[read] != arr[write-1]), move zeroes (arr[read] != 0), remove element (arr[read] != val), remove even numbers — the structure is identical. - Only the condition changes.
05
Section Five · Fast & Slow
Pattern 3 — Fast & Slow Pointers (Floyd's)
Fast pointer moves 2 steps per iteration, slow pointer moves 1 step. If there's a cycle, they meet inside it. If there's no cycle, fast reaches the end. This is Floyd's cycle detection algorithm — O(n) time, O(1) space. Beyond cycle detection, the same technique finds the middle of a linked list (when fast reaches the end, slow is at the middle) and detects cycles in abstract sequences (like "Happy Number" LC 202).
Pseudocode — Linked List Cycle Detection
function hasCycle(head):
slow = head, fast = head
while fast != null and fast.next != null:
slow = slow.next // 1 step
fast = fast.next.next // 2 steps if slow == fast:
return true // met inside cycle return false // fast reached end → no cycle // O(n), O(1) space
Floyd's Cycle Detection — fast catches slow inside the cycle
Find Middle Node — Fast/Slow
function findMiddle(head):
slow = head, fast = head
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
return slow // slow is at the middle
Floyd's algorithm also finds the cycle START:
- After slow and fast meet inside the cycle, reset one pointer to head.
- Move both at speed 1 — they meet again at the cycle's entry point.
- This solves LC 142 "Linked List Cycle II" and is provable mathematically: if the tail has length a and the cycle has length c, they meet at distance a from the cycle start.
06
Section Six · Merge Pattern
Pattern 4 — Merge Two Sequences
Two pointers, each starting at the beginning of a different sorted sequence. Compare the two pointed elements, process the smaller one, advance that pointer. Continues until both sequences are exhausted. This is the merge step of Merge Sort, and the basis of "Merge Sorted Array" (LC 88), "Merge Two Sorted Lists" (LC 21), and "Intersection of Two Arrays" (LC 349).
Pseudocode — Merge Two Sorted Arrays
function merge(A, B):
i = 0, j = 0
result = []
while i < A.length and j < B.length:
if A[i] <= B[j]:
result.add(A[i++])
else:
result.add(B[j++])
// copy remaining elements from A or B while i < A.length: result.add(A[i++])
while j < B.length: result.add(B[j++])
return result // O(n + m)
Merge in-place (LC 88 trick):
- When merging into array A which has enough space, fill from the END (right to left) — compare the largest unplaced elements and put them at the back.
- This avoids overwriting unprocessed elements:
A[k--] = A[i] > B[j] ? A[i--] : B[j--].
07
Section Seven · When to Use
Choosing the Right Pattern
| Signal | Pattern | Examples |
|---|---|---|
| Sorted array + find pair with property | Opposite ends | Two Sum II, 3Sum, Container |
| Remove/compact elements in-place | Read/write (same dir) | Remove Dups, Move Zeroes |
| Cycle in linked list or sequence | Fast/slow | Cycle Detection, Happy Number |
| Middle of linked list | Fast/slow | Middle Node, Palindrome LL |
| Merge two sorted sequences | Merge (two inputs) | Merge Array, Merge Lists |
| Palindrome check | Opposite ends | Valid Palindrome |
| Three values (Dutch flag) | Three pointers | Sort Colors (LC 75) |
08
Section Eight · Implementation
Build It Once
Build each pattern once — they're short enough to memorise. In interviews, the code is 5–10 lines; the hard part is recognising which pattern to apply.
Java — All four patterns
// 1. Opposite ends — Two Sum II — O(n) int[] twoSum(int[] arr, int target) {
int L = 0, R = arr.length - 1;
while (L < R) {
int sum = arr[L] + arr[R];
if (sum == target) return new int[]{L, R};
else if (sum < target) L++;
else R--;
}
return new int[]{-1, -1};
}
// 2. Read/write — Remove Duplicates — O(n), O(1) int removeDuplicates(int[] arr) {
if (arr.length == 0) return 0;
int w = 1;
for (int r = 1; r < arr.length; r++)
if (arr[r] != arr[r - 1]) arr[w++] = arr[r];
return w;
}
// 3. Fast/slow — Cycle detection — O(n), O(1) boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
Two Pointers — Full Implementation
Java — All two-pointer patterns
import java.util.*;
public class TwoPointers {
// ═══ 1. Two Sum II (opposite ends) ═══════ O(n) static int[] twoSum(int[] arr, int target) {
int L = 0, R = arr.length - 1;
while (L < R) {
int s = arr[L] + arr[R];
if (s == target) return new int[]{L + 1, R + 1};
else if (s < target) L++;
else R--;
}
return new int[]{-1, -1};
}
// ═══ 2. 3Sum (sort + opposite ends) ══════ O(n²) static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip dups int L = i + 1, R = nums.length - 1;
while (L < R) {
int s = nums[i] + nums[L] + nums[R];
if (s == 0) {
res.add(Arrays.asList(nums[i], nums[L], nums[R]));
while (L < R && nums[L] == nums[L + 1]) L++;
while (L < R && nums[R] == nums[R - 1]) R--;
L++; R--;
} else if (s < 0) L++;
else R--;
}
}
return res;
}
// ═══ 3. Container With Most Water ════════ O(n) static int maxArea(int[] h) {
int L = 0, R = h.length - 1, max = 0;
while (L < R) {
max = Math.max(max, (R - L) * Math.min(h[L], h[R]));
if (h[L] < h[R]) L++; else R--;
}
return max;
}
// ═══ 4. Remove Duplicates (read/write) ═══ O(n) static int removeDuplicates(int[] arr) {
if (arr.length == 0) return 0;
int w = 1;
for (int r = 1; r < arr.length; r++)
if (arr[r] != arr[r - 1]) arr[w++] = arr[r];
return w;
}
// ═══ 5. Move Zeroes (read/write) ═════════ O(n) static void moveZeroes(int[] arr) {
int w = 0;
for (int r = 0; r < arr.length; r++)
if (arr[r] != 0) arr[w++] = arr[r];
while (w < arr.length) arr[w++] = 0;
}
// ═══ 6. Valid Palindrome (opposite ends) ═ O(n) static boolean isPalindrome(String s) {
int L = 0, R = s.length() - 1;
while (L < R) {
while (L < R && !Character.isLetterOrDigit(s.charAt(L))) L++;
while (L < R && !Character.isLetterOrDigit(s.charAt(R))) R--;
if (Character.toLowerCase(s.charAt(L)) != Character.toLowerCase(s.charAt(R)))
return false;
L++; R--;
}
return true;
}
// ═══ 7. Sort Colors — Dutch National Flag ═ O(n) static void sortColors(int[] arr) {
int lo = 0, mid = 0, hi = arr.length - 1;
while (mid <= hi) {
if (arr[mid] == 0) { swap(arr, lo++, mid++); }
else if (arr[mid] == 1) { mid++; }
else { swap(arr, mid, hi--); }
}
}
static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
// ═══ Main ═══════════════════════════════════ public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2,7,11,15}, 9)));
System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4}));
System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
}
}
Python — Two-pointer implementations
# ═══ 1. Two Sum II (opposite ends) ═══════ O(n) def two_sum(arr, target):
L, R = 0, len(arr) - 1
while L < R:
s = arr[L] + arr[R]
if s == target: return [L + 1, R + 1]
elif s < target: L += 1
else: R -= 1
return [-1, -1]
# ═══ 2. 3Sum ══════════════════════════════ O(n²) def three_sum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue
L, R = i + 1, len(nums) - 1
while L < R:
s = nums[i] + nums[L] + nums[R]
if s == 0:
res.append([nums[i], nums[L], nums[R]])
while L < R and nums[L] == nums[L+1]: L += 1
while L < R and nums[R] == nums[R-1]: R -= 1
L += 1; R -= 1
elif s < 0: L += 1
else: R -= 1
return res
# ═══ 3. Remove Duplicates (read/write) ════ O(n) def remove_duplicates(arr):
if not arr: return 0
w = 1
for r in range(1, len(arr)):
if arr[r] != arr[r-1]:
arr[w] = arr[r]; w += 1
return w
# ═══ 4. Move Zeroes ═══════════════════════ O(n) def move_zeroes(arr):
w = 0
for r in range(len(arr)):
if arr[r] != 0:
arr[w] = arr[r]; w += 1
while w < len(arr):
arr[w] = 0; w += 1
# ═══ 5. Cycle Detection (fast/slow) ═══════ O(n) def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return True return False # ═══ 6. Valid Palindrome ══════════════════ O(n) def is_palindrome(s):
L, R = 0, len(s) - 1
while L < R:
while L < R and not s[L].isalnum(): L += 1
while L < R and not s[R].isalnum(): R -= 1
if s[L].lower() != s[R].lower(): return False
L += 1; R -= 1
return True # Demo
print(two_sum([2,7,11,15], 9)) # [1, 2]
print(three_sum([-1,0,1,2,-1,-4])) # [[-1,-1,2],[-1,0,1]]
print(is_palindrome("A man, a plan, a canal: Panama")) # True
09
Section Nine · Java Reference
Use It In Java
IN JAVA — Two-Pointer Idioms
Array index
int L = 0, R = arr.length - 1; — most common form ListNode
ListNode slow = head, fast = head; — linked list traversal | Pattern | Loop condition | Key idiom |
|---|---|---|
| Opposite ends | while (L < R) | L++ or R-- based on comparison |
| Read/write | for (r = 0; r < n; r++) | arr[w++] = arr[r] when condition met |
| Fast/slow | while (fast != null && fast.next != null) | slow = slow.next; fast = fast.next.next |
| Merge | while (i < m && j < n) | Take smaller, advance that pointer |
| 3Sum | outer for + inner while (L < R) | Skip duplicates with while (nums[L]==nums[L+1]) L++ |
⚠ Gotcha: In the fast/slow linked list pattern, always check
fast != null && fast.next != null BEFORE accessing fast.next.next — otherwise you get a NullPointerException on odd-length lists. The order of the null check matters: fast first, then fast.next.
⚠ Gotcha: In 3Sum, skipping duplicates requires checking AFTER adding a result —
while (L < R && nums[L] == nums[L+1]) L++. Skipping before checking misses valid triplets; skipping after ensures you find at least one instance of each unique triplet.
10
Section Ten · Practice
Problems To Solve
Two-pointer problems test pattern recognition more than coding skill — every problem is 5–15 lines once you identify the right pattern. The challenge is knowing whether to use opposite ends (sorted pair), read/write (in-place compact), or fast/slow (linked list). Read the problem constraints: sorted array + pair → opposite ends. In-place + O(1) space → read/write. Linked list + cycle or middle → fast/slow.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | opposite | Two Sum II — LC 167 | Sorted array, find pair with target sum. L at start, R at end. Sum too small → L++. Sum too big → R--. O(n). |
| Easy | opposite | Valid Palindrome — LC 125 | L and R converge from opposite ends, skipping non-alphanumeric characters. Compare lowercase characters at each step. |
| Easy | read/write | Move Zeroes — LC 283 | Write pointer compacts non-zero elements to the front. Fill remaining positions with 0. O(n), O(1). |
| Medium | opposite | 3Sum — LC 15 | Sort + fix one element + two-pointer on the rest. Skip duplicates at both the outer loop and inner two-pointer to avoid duplicate triplets. |
| Medium | opposite | Container With Most Water — LC 11 | Opposite ends. Area = width × min(height). Move the shorter side inward — the only direction that can increase the limiting height. |
| Medium | fast/slow | Linked List Cycle II — LC 142 | Fast/slow to detect cycle. Then reset one to head, advance both at speed 1 — they meet at the cycle entry point. Mathematical proof: tail length = remaining cycle distance. |
Interview Pattern:
- Two pointers is the most concise technique — every solution is under 15 lines.
- The interview skill is not writing the code but recognising the pattern. Sorted + pair → opposite ends.
- In-place filter → read/write. Linked list structure → fast/slow. Once you identify the pattern, the code writes itself.