--- # === IDENTITY === id: software/patterns/two-pointer-technique/2026 canonical_question: "How do I apply the two-pointer technique?" aliases: - "two pointer algorithm" - "opposite direction pointers" - "fast and slow pointers" - "converging pointers technique" - "sliding window two pointers" - "two pointer pattern for arrays and linked lists" - "Floyd's tortoise and hare" entity_type: software_reference domain: software > patterns > two-pointer-technique region: global jurisdiction: global temporal_scope: 2026-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Opposite-direction pointers require the input to be sorted (or the problem must be order-independent like container with most water)" - "Fast/slow pointer cycle detection assumes a singly linked list or sequence with at most one cycle entry point" - "Never mutate the collection being traversed in-place if both pointers index into it — use a separate write pointer or copy" - "Two-pointer does not generalize to unsorted arrays for pair-sum problems without O(n) extra space (use a hash map instead)" - "Always guard against off-by-one: ensure both pointers stay within bounds on every iteration" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need to find subarrays with a dynamic size constraint (e.g., longest substring with at most K distinct characters)" use_instead: "software/patterns/sliding-window-technique/2026" - condition: "Need to search for a single element in a sorted collection" use_instead: "software/patterns/binary-search-variations/2026" - condition: "Need O(1) lookup for pair-sum in an unsorted array" use_instead: "Use a hash map / hash set approach" # === AGENT HINTS === inputs_needed: - key: pointer_type question: "Which two-pointer variant does your problem require?" type: choice options: ["opposite ends (converging)", "same direction (fast/slow)", "same direction (read/write)", "partitioning"] - key: data_structure question: "What data structure are you working with?" type: choice options: ["sorted array", "unsorted array", "string", "singly linked list"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/two-pointer-technique/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/sliding-window-technique/2026" label: "Sliding Window Technique" - id: "software/patterns/binary-search-variations/2026" label: "Binary Search Variations" - id: "software/patterns/sorting-algorithms/2026" label: "Sorting Algorithms" solves: [] alternative_to: [] often_confused_with: - id: "software/patterns/sliding-window-technique/2026" label: "Sliding Window Technique (same-direction pointers with a window, not a pair)" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Two Pointers Technique" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/two-pointers-technique/ type: community_resource published: 2024-12-15 reliability: high - id: src2 title: "Two Pointers Introduction" author: AlgoMonster url: https://algo.monster/problems/two_pointers_intro type: technical_blog published: 2024-06-01 reliability: high - id: src3 title: "Two-Pointer Overview" author: Hello Interview url: https://www.hellointerview.com/learn/code/two-pointers/overview type: technical_blog published: 2025-01-10 reliability: moderate_high - id: src4 title: "Java Two Pointer Technique" author: Baeldung url: https://www.baeldung.com/java-two-pointer-technique type: technical_blog published: 2024-08-20 reliability: high - id: src5 title: "Two Pointer Techniques for Array Problems" author: labuladong url: https://labuladong.online/algo/en/essential-technique/array-two-pointers-summary/ type: technical_blog published: 2024-11-05 reliability: moderate_high - id: src6 title: "Two Pointers - USACO Guide" author: USACO Guide url: https://usaco.guide/silver/two-pointers type: community_resource published: 2024-09-01 reliability: high - id: src7 title: "The Two Pointer Technique: A Complete Guide" author: LeetCopilot url: https://leetcopilot.dev/leetcode-pattern/two-pointers/guide type: technical_blog published: 2025-02-01 reliability: moderate_high --- # Two-Pointer Technique: Complete Reference ## TL;DR - **Bottom line**: The two-pointer technique uses two index variables traversing a data structure in a coordinated way to reduce O(n^2) brute-force solutions to O(n) time with O(1) extra space. - **Key pattern**: `left, right = 0, len(arr)-1; while left < right: move based on condition` - **Watch out for**: Applying two pointers to unsorted data when the algorithm assumes sorted order. - **Works with**: Arrays, strings, linked lists. Language-agnostic; no dependencies. ## Constraints - Opposite-direction (converging) pointers require sorted input or a problem where order does not affect correctness (e.g., container with most water) - Fast/slow pointer cycle detection only works on linked lists or sequences with a single entry point into a cycle - Never modify the collection under iteration from both pointer positions simultaneously without a dedicated write pointer - Two pointers cannot replace a hash map for pair-sum on unsorted arrays without first sorting (adding O(n log n)) - Always validate that both pointers remain within bounds on every step; off-by-one errors are the top source of bugs ## Quick Reference | Pattern | Pointer Init | Movement Rule | Time | Space | Classic Problems | |---|---|---|---|---|---| | Opposite ends (converging) | `left=0, right=n-1` | Move the pointer that improves the objective | O(n) | O(1) | Two Sum II, Container With Most Water, Trapping Rain Water, Valid Palindrome | | Same direction (read/write) | `slow=0, fast=0` | Fast scans all elements; slow marks write position | O(n) | O(1) | Remove Duplicates from Sorted Array, Remove Element, Move Zeroes | | Fast/slow (cycle detection) | `slow=head, fast=head` | Slow moves 1 step, fast moves 2 steps | O(n) | O(1) | Linked List Cycle, Find the Duplicate Number, Happy Number | | Fast/slow (midpoint) | `slow=head, fast=head` | Slow moves 1, fast moves 2; stop when fast reaches end | O(n) | O(1) | Middle of the Linked List, Palindrome Linked List | | Partitioning | `lo=0, hi=n-1` | Swap elements that belong on the other side | O(n) | O(1) | Sort Colors (Dutch National Flag), Partition Array | | Merge (two arrays) | `i=0, j=0` | Advance the pointer with the smaller element | O(n+m) | O(n+m) | Merge Sorted Array, Intersection of Two Arrays | | Expand from center | `left=center, right=center` | Expand outward while condition holds | O(n^2) total | O(1) | Longest Palindromic Substring | | Three pointers | `lo=0, mid=0, hi=n-1` | Partition into three regions | O(n) | O(1) | Sort Colors, Dutch National Flag | ## Decision Tree ``` START |-- Is the input a linked list? | |-- YES: Need cycle detection? | | |-- YES --> Fast/slow pointers (Floyd's algorithm) | | |-- NO: Need the middle node? | | |-- YES --> Fast/slow (stop when fast reaches end) | | |-- NO --> Same-direction pointers | |-- NO (array or string) | |-- Is the input sorted (or can you sort it)? | |-- YES: Looking for a pair that satisfies a condition? | | |-- YES --> Opposite-ends (converging) pointers | | |-- NO: Need to remove/deduplicate in-place? | | |-- YES --> Same-direction read/write pointers | | |-- NO --> Consider binary search instead | |-- NO (unsorted): | |-- Can you afford O(n log n) sorting first? | | |-- YES --> Sort, then use converging pointers | | |-- NO --> Use a hash map/set instead (O(n) time, O(n) space) |-- Need to partition into regions (e.g., pivot)? | |-- YES --> Three-pointer / Dutch National Flag |-- Need longest/shortest substring with a constraint? | |-- YES --> Sliding window (see related unit) |-- DEFAULT --> Brute force or hash map ``` ## Step-by-Step Guide ### 1. Identify the pointer pattern Determine which variant fits your problem. If you need to find a pair in a sorted array, use converging pointers. If you need to detect a cycle, use fast/slow. If you need to remove elements in-place, use read/write pointers. [src1] **Verify**: Can you express the loop invariant? e.g., "Everything to the left of `slow` is processed and valid." ### 2. Initialize pointers correctly For converging: `left = 0, right = len(arr) - 1`. For same-direction: `slow = 0, fast = 0` (or `fast = 1`). For linked lists: `slow = head, fast = head`. [src2] **Verify**: Both pointers point to valid positions in the data structure before the loop starts. ### 3. Define the loop condition Converging: `while left < right`. Same-direction: `while fast < len(arr)`. Linked list: `while fast is not None and fast.next is not None`. [src5] **Verify**: The loop terminates in all cases. Converging pointers always reduce the gap by at least 1 per iteration. ### 4. Implement the movement logic Inside the loop, decide which pointer to advance based on the problem condition. For converging pointers on two-sum: if `arr[left] + arr[right] < target`, increment `left`; if greater, decrement `right`; if equal, return the pair. [src1] **Verify**: Each iteration advances at least one pointer, guaranteeing O(n) termination. ### 5. Handle edge cases Empty input, single element, all duplicates, already-at-target. For linked lists: null head, single node, cycle that includes the head. [src3] **Verify**: Test with arrays of length 0, 1, 2 and linked lists with 0, 1, 2 nodes. ## Code Examples ### Python: Two Sum on Sorted Array (Converging Pointers) ```python # Input: sorted array of integers, integer target # Output: tuple of 1-indexed positions (i, j) where arr[i]+arr[j]==target def two_sum_sorted(numbers: list[int], target: int) -> tuple[int, int]: left, right = 0, len(numbers) - 1 while left < right: current = numbers[left] + numbers[right] if current == target: return (left + 1, right + 1) # 1-indexed elif current < target: left += 1 # need a larger sum else: right -= 1 # need a smaller sum raise ValueError("No solution found") ``` ### Python: Container With Most Water (Converging Pointers) ```python # Input: list of non-negative integers representing heights # Output: maximum water area between any two lines def max_area(height: list[int]) -> int: left, right = 0, len(height) - 1 best = 0 while left < right: width = right - left h = min(height[left], height[right]) best = max(best, width * h) if height[left] < height[right]: left += 1 # move the shorter line inward else: right -= 1 return best ``` ### JavaScript: Remove Duplicates In-Place (Read/Write Pointers) ```javascript // Input: sorted array of integers (nums) // Output: length of array with duplicates removed; nums mutated in-place function removeDuplicates(nums) { if (nums.length === 0) return 0; let slow = 0; // write pointer for (let fast = 1; fast < nums.length; fast++) { if (nums[fast] !== nums[slow]) { // found a new unique element slow++; nums[slow] = nums[fast]; // write it at the next position } } return slow + 1; // length of unique portion } ``` ### Python: Linked List Cycle Detection (Floyd's Algorithm) ```python # Input: head of a singly linked list (may contain a cycle) # Output: True if cycle exists, False otherwise class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def has_cycle(head: ListNode | None) -> bool: slow = fast = head while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps if slow is fast: # pointers met inside the cycle return True return False # fast reached end; no cycle ``` ### Java: Valid Palindrome (Converging Pointers with Filtering) ```java // Input: string s with mixed characters // Output: true if s is a palindrome considering only alphanumeric chars public boolean isPalindrome(String s) { int left = 0, right = s.length() - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++; // skip non-alphanumeric while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--; // skip non-alphanumeric if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false; left++; right--; } return true; } ``` ## Anti-Patterns ### Wrong: Using two pointers on unsorted data for pair-sum ```python # BAD -- two-pointer converging requires sorted input def two_sum_wrong(nums, target): left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return [left, right] elif s < target: left += 1 else: right -= 1 return [] # may miss valid pairs because array is unsorted ``` ### Correct: Sort first or use a hash map ```python # GOOD -- sort first, then use converging pointers def two_sum_correct(nums, target): indexed = sorted(enumerate(nums), key=lambda x: x[1]) left, right = 0, len(indexed) - 1 while left < right: s = indexed[left][1] + indexed[right][1] if s == target: return [indexed[left][0], indexed[right][0]] elif s < target: left += 1 else: right -= 1 return [] # OR: use a hash map for O(n) without sorting def two_sum_hashmap(nums, target): seen = {} for i, n in enumerate(nums): complement = target - n if complement in seen: return [seen[complement], i] seen[n] = i return [] ``` ### Wrong: Not skipping duplicates in 3Sum ```python # BAD -- produces duplicate triplets def three_sum_wrong(nums, target=0): nums.sort() result = [] for i in range(len(nums) - 2): left, right = i + 1, len(nums) - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s == target: result.append([nums[i], nums[left], nums[right]]) left += 1 right -= 1 elif s < target: left += 1 else: right -= 1 return result # contains duplicate triplets ``` ### Correct: Skip duplicate values after finding a match ```python # GOOD -- skip duplicates at all three positions def three_sum_correct(nums, target=0): nums.sort() result = [] for i in range(len(nums) - 2): if i > 0 and nums[i] == nums[i - 1]: # skip duplicate i continue left, right = i + 1, len(nums) - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s == target: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 # skip duplicate left while left < right and nums[right] == nums[right - 1]: right -= 1 # skip duplicate right left += 1 right -= 1 elif s < target: left += 1 else: right -= 1 return result ``` ### Wrong: Incorrect fast/slow pointer initialization for cycle start ```python # BAD -- returns the wrong node as cycle start def find_cycle_start_wrong(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return slow # this is the meeting point, NOT the cycle start return None ``` ### Correct: Reset one pointer to head after detection ```python # GOOD -- Floyd's algorithm phase 2: find the cycle entry def find_cycle_start_correct(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # Phase 2: move one pointer to head, advance both by 1 slow = head while slow != fast: slow = slow.next fast = fast.next return slow # this is the actual cycle entry node return None ``` ## Common Pitfalls - **Off-by-one in loop condition**: Using `left <= right` instead of `left < right` for pair-finding causes accessing the same element twice. Fix: use `left < right` for distinct pairs. [src1] - **Forgetting to sort**: Converging pointers on unsorted data silently produces wrong results with no error. Fix: always `sort()` first or verify the input is pre-sorted. [src3] - **Infinite loop from not advancing pointers**: If neither pointer moves when a condition is not met, the loop never terminates. Fix: ensure at least one pointer advances on every iteration. [src5] - **Mutating during traversal**: Writing to `arr[fast]` while also reading from `arr[slow]` when `slow == fast` causes data corruption. Fix: use distinct read and write pointers that never overlap incorrectly. [src4] - **Not handling duplicates**: In problems like 3Sum, failing to skip duplicate values produces redundant results and wastes time. Fix: after finding a match, advance pointers past all equal elements. [src6] - **Assuming fast/slow works on doubly linked lists**: The tortoise-and-hare algorithm does not detect cycles in doubly linked lists (a node with `prev` and `next` always forms a trivial "cycle"). Fix: use a hash set for doubly linked lists. [src2] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Finding a pair in a sorted array with a target sum | Array is unsorted and you cannot afford O(n log n) sort | Hash map (O(n) time, O(n) space) | | Removing duplicates or elements in-place from a sorted array | You need to preserve original indices or order of unsorted elements | Filter into a new array | | Detecting cycles in a singly linked list | Working with a doubly linked list or graph | Hash set / DFS with visited set | | Checking if a string is a palindrome | Need to find all palindromic substrings | Expand-from-center or Manacher's algorithm | | Merging two sorted arrays | Arrays are unsorted | Sort first, or use a heap for k-way merge | | Partitioning an array (Dutch National Flag) | Need stable partitioning (preserve relative order) | Stable partition with O(n) extra space | | Container with most water / trapping rain water | Problem has non-monotonic objective with no greedy elimination | Dynamic programming or monotonic stack | ## Important Caveats - The two-pointer technique is a conceptual pattern, not a specific algorithm. Its correctness depends entirely on the problem's structure (monotonicity, sorted order, or cycle properties). - When sorting is required as a preprocessing step, the overall complexity becomes O(n log n), not O(n). The two-pointer traversal itself is O(n), but the sort dominates. - For problems on strings with Unicode characters, pointer arithmetic on byte indices can be wrong. Always iterate by character (e.g., Python handles this natively; in Java/JavaScript, use code point iteration for astral plane characters). - The fast/slow pointer technique for finding the cycle entry point relies on a mathematical proof (distance relationship). Simply detecting the meeting point is not sufficient to find the cycle start; you must reset one pointer to the head. - Two-pointer solutions often have subtle edge cases with empty inputs, single-element inputs, and all-equal elements. Always test these boundary conditions. ## Related Units - [Sliding Window Technique](/software/patterns/sliding-window-technique/2026) - [Binary Search Variations](/software/patterns/binary-search-variations/2026) - [Sorting Algorithms](/software/patterns/sorting-algorithms/2026)