7a:T439,Imagine you're given a sorted array and asked to find two numbers that add up to a target sum. The naive approach—checking every possible pair—requires O(n²) time. But what if you could solve this in a single pass through the array? What if, instead of checking n² pairs, you could find the answer by examining at most n elements? This is the power of the **two-pointer technique**: a deceptively simple algorithmic pattern that transforms quadratic-time brute-force solutions into elegant linear-time algorithms. It's one of the most frequently used patterns in technical interviews, appearing in countless problems from array manipulation to string processing to linked list traversal. The technique is exactly what it sounds like: you maintain **two pointers** (or indices) that traverse your data structure according to specific rules. But the elegance lies in how these rules are designed—each pointer movement eliminates large swaths of the search space, allowing you to solve problems that would otherwise require nested loops with a single, intelligent traversal.72:{"json":{"id":"seed_6e2aad11dc0ebc3f752f3a1c26c59968","slug":"two-pointer-technique","category":"Data Structures & Algorithms","topic":"Two-Pointer Technique","title":"The Two-Pointer Technique","description":"Master the two-pointer technique—a fundamental algorithmic pattern that transforms brute-force solutions into elegant, efficient algorithms. Learn same-direction and opposite-direction pointer strategies, apply them to classic problems, and develop the pattern recognition to know when this technique applies.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_7f6885304035f2a2f9365cb2ee4c0fe1","title":"What is the Two-Pointer Technique","order":0,"content":[{"id":"opening-hook","title":"The Pattern That Transforms Quadratic into Linear","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the fundamental concept of the two-pointer technique, why it works, and how to recognize problems where it applies. You'll gain the mental model that makes this pattern intuitive rather than a trick to memorize.","variant":"info"},"type":"callout"}]},{"id":"core-concept","title":"The Core Concept","content":[{"data":{"content":"At its heart, the two-pointer technique is about **structured exploration**. Instead of exhaustively examining every possibility, you use two pointers that move through the data in a coordinated way, making intelligent decisions about which possibilities to skip.\n\n**The fundamental insight:**\n\nIn many problems, the brute-force approach examines pairs (or subsequences) that can be logically eliminated. The two-pointer technique exploits this by:\n\n1. **Starting from strategic positions** (e.g., both ends of an array, or both at the beginning)\n2. **Moving based on comparison outcomes** (e.g., if the sum is too small, move one pointer to increase it)\n3. **Guaranteeing completeness** (every valid solution is considered, even if most are skipped)\n\nThis is not a heuristic or approximation—when applicable, the two-pointer technique gives **correct** answers in **optimal** time."},"type":"text"},{"data":{"icon":"Info","title":"A Pointer Is Just an Index","content":"In the context of arrays, a 'pointer' is simply an integer index. We call them pointers because they 'point' to specific positions in the array. The same concept applies to linked lists (where they're actual node references) and strings (where they're character positions). The technique remains the same regardless of the underlying data structure.","variant":"note"},"type":"callout"},{"data":{"content":"**Visualizing the technique:**\n\nConsider an array `[1, 3, 5, 7, 9]` and imagine two pointers—one at the start (`left = 0`) and one at the end (`right = 4`). They're looking at values 1 and 9.\n\n```\nArray: [1, 3, 5, 7, 9]\n ↑ ↑\n left right\n (value=1) (value=9)\n```\n\nNow, each pointer can move inward. If we're searching for a target sum:\n- If the current sum is too small, we need a larger value → move `left` right\n- If the current sum is too large, we need a smaller value → move `right` left\n- If we've found the target, we're done\n\nEach movement shrinks the search space, and we never revisit a position. This is why the algorithm is O(n)—each pointer moves at most n times total."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"why-two-pointers","title":"Why Two Pointers Work","content":[{"data":{"content":"The two-pointer technique works because of a crucial property: **each pointer movement logically eliminates multiple possibilities**.\n\nLet's prove this with the two-sum problem on a sorted array. Given `[1, 3, 5, 7, 9]` with target `10`:"},"type":"text"},{"data":{"rows":[["1","0","4","1","9","10","Found! (1 + 9 = 10)"]],"caption":"Two-Pointer Walk-Through: Finding Two Numbers That Sum to 10","headers":["Step","Left Index","Right Index","Left Value","Right Value","Sum","Action"]},"type":"table"},{"data":{"content":"In this case, we got lucky and found the answer immediately. But let's try target `8`:"},"type":"text"},{"data":{"rows":[["1","0","4","1","9","10","Too large → move right left"],["2","0","3","1","7","8","Found! (1 + 7 = 8)"]],"caption":"Two-Pointer Walk-Through: Finding Two Numbers That Sum to 8","headers":["Step","Left Index","Right Index","Left Value","Right Value","Sum","Action"]},"type":"table"},{"data":{"content":"**Why moving `right` left was correct:**\n\nWhen `1 + 9 = 10 > 8`, we knew that `9` was too large. But here's the key insight: since the array is sorted, pairing `9` with **any** element to the left of the current left pointer would give an even smaller sum, and we need a larger sum partner for those smaller elements. However, since `9` is already too large for our smallest remaining element (`1`), it's too large for **all** remaining elements. Therefore, we can eliminate `9` from consideration entirely.\n\nThis is the secret sauce: **one comparison eliminates an entire row or column of the pair matrix**."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Pair Matrix Mental Model","content":"Think of all possible pairs as a 2D matrix where rows are left indices and columns are right indices. The brute-force approach examines every cell. The two-pointer technique starts at a corner and moves either down a row or left a column based on each comparison—but each move eliminates an entire row or column. That's why n² pairs can be handled in O(n) movements.","variant":"tip"},"type":"callout"},{"data":{"content":"**The invariant that makes it work:**\n\nThroughout the algorithm, we maintain an important invariant: *all pairs with left indices < current left or right indices > current right have already been implicitly considered and rejected*.\n\nWhen we move `left` right, we're saying \"all pairs involving the old `left` index have been handled.\"\nWhen we move `right` left, we're saying \"all pairs involving the old `right` index have been handled.\"\n\nAt termination, every pair has been considered—most were eliminated without explicit examination, but the logic guarantees they weren't valid solutions."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"fundamental-variants","title":"The Two Fundamental Variants","content":[{"data":{"content":"Two-pointer techniques come in two primary flavors, each suited to different problem types:"},"type":"text"},{"data":{"left":[{"data":{"items":["Pointers start at **opposite ends**","Move **toward each other** based on conditions","Useful for: pair sums, palindrome checks, container problems","Terminates when pointers meet or cross","Works when data has **ordering** that informs movement"],"title":{"icon":"Target","text":"Opposite-Direction (Converging)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Both pointers start at the **same position**","Move at **different speeds or conditions**","Useful for: removing duplicates, partitioning, cycle detection","Terminates when fast pointer reaches the end (or cycles)","Works when you need to **track two positions** during traversal"],"title":{"icon":"Zap","text":"Same-Direction (Fast & Slow)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**When to use which variant:**"},"type":"text"},{"data":{"rows":[["Need to find pairs with a property","Opposite-direction"],["Data is sorted and you're searching","Opposite-direction"],["Checking symmetry (palindromes)","Opposite-direction"],["In-place modifications while traversing","Same-direction"],["Partitioning elements by condition","Same-direction"],["Detecting cycles or meeting points","Same-direction"]],"headers":["Problem Characteristic","Suggested Variant"]},"type":"table"},{"data":{"content":"The choice isn't always obvious, but pattern recognition comes quickly with practice."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"brute-to-two-pointer","title":"The Brute-Force to Two-Pointer Transformation","content":[{"data":{"content":"One of the most valuable skills is recognizing when a brute-force solution can be transformed into a two-pointer solution. Let's see this transformation explicitly.\n\n**Problem:** Given a sorted array, find if there exist two elements whose sum equals a target value."},"type":"text"},{"data":{"tabs":[{"id":"brute-force","badge":"O(n²)","label":"Brute Force","content":[{"data":{"fileName":"brute_force_two_sum.py","languages":[{"code":"def has_pair_with_sum_brute(arr: list[int], target: int) -> bool:\n \"\"\"\n Brute force: Check every possible pair.\n Time: O(n²) - two nested loops\n Space: O(1) - no extra space\n \"\"\"\n n = len(arr)\n \n # For each element i\n for i in range(n):\n # Check every element j > i\n for j in range(i + 1, n):\n if arr[i] + arr[j] == target:\n return True # Found a pair\n \n return False # No pair found\n\n# Example usage\narr = [1, 3, 5, 7, 9]\nprint(has_pair_with_sum_brute(arr, 8)) # True (1 + 7)\nprint(has_pair_with_sum_brute(arr, 20)) # False","label":"Python","value":"python"},{"code":"function hasPairWithSumBrute(arr, target) {\n /**\n * Brute force: Check every possible pair.\n * Time: O(n²) - two nested loops\n * Space: O(1) - no extra space\n */\n const n = arr.length;\n \n // For each element i\n for (let i = 0; i < n; i++) {\n // Check every element j > i\n for (let j = i + 1; j < n; j++) {\n if (arr[i] + arr[j] === target) {\n return true; // Found a pair\n }\n }\n }\n \n return false; // No pair found\n}\n\n// Example usage\nconst arr = [1, 3, 5, 7, 9];\nconsole.log(hasPairWithSumBrute(arr, 8)); // true (1 + 7)\nconsole.log(hasPairWithSumBrute(arr, 20)); // false","label":"JavaScript","value":"javascript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"The brute-force approach checks all n(n-1)/2 pairs. For an array of 10,000 elements, that's nearly 50 million comparisons. The nested loop structure is the telltale sign of O(n²) complexity."},"type":"text"}],"titleIcon":"XCircle"},{"id":"two-pointer","badge":"O(n)","label":"Two-Pointer","content":[{"data":{"fileName":"two_pointer_two_sum.py","languages":[{"code":"def has_pair_with_sum(arr: list[int], target: int) -> bool:\n \"\"\"\n Two-pointer approach: Exploit sorted order.\n Time: O(n) - single pass with two pointers\n Space: O(1) - only two index variables\n \n Key insight: In a sorted array, moving left pointer\n increases the sum, moving right pointer decreases it.\n \"\"\"\n left = 0\n right = len(arr) - 1\n \n while left < right:\n current_sum = arr[left] + arr[right]\n \n if current_sum == target:\n return True # Found the pair\n elif current_sum < target:\n # Sum too small, need larger values\n left += 1\n else:\n # Sum too large, need smaller values\n right -= 1\n \n return False # Pointers crossed, no pair found\n\n# Example usage\narr = [1, 3, 5, 7, 9]\nprint(has_pair_with_sum(arr, 8)) # True (1 + 7)\nprint(has_pair_with_sum(arr, 20)) # False","label":"Python","value":"python"},{"code":"function hasPairWithSum(arr, target) {\n /**\n * Two-pointer approach: Exploit sorted order.\n * Time: O(n) - single pass with two pointers\n * Space: O(1) - only two index variables\n * \n * Key insight: In a sorted array, moving left pointer\n * increases the sum, moving right pointer decreases it.\n */\n let left = 0;\n let right = arr.length - 1;\n \n while (left < right) {\n const currentSum = arr[left] + arr[right];\n \n if (currentSum === target) {\n return true; // Found the pair\n } else if (currentSum < target) {\n // Sum too small, need larger values\n left++;\n } else {\n // Sum too large, need smaller values\n right--;\n }\n }\n \n return false; // Pointers crossed, no pair found\n}\n\n// Example usage\nconst arr = [1, 3, 5, 7, 9];\nconsole.log(hasPairWithSum(arr, 8)); // true (1 + 7)\nconsole.log(hasPairWithSum(arr, 20)); // false","label":"JavaScript","value":"javascript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"The two-pointer approach makes at most n iterations total (each pointer moves at most n/2 times toward the center). For 10,000 elements, that's at most 10,000 operations—a 5000x improvement over brute force."},"type":"text"}],"titleIcon":"CheckCircle"}],"defaultTab":"two-pointer"},"type":"tabs"},{"data":{"icon":"AlertCircle","title":"Prerequisite: Sorted Data","content":"The opposite-direction two-pointer technique for pair sums requires sorted data. If the input isn't sorted, you have two options: (1) Sort first in O(n log n), making total time O(n log n), or (2) Use a hash set for O(n) time but O(n) space. The two-pointer technique on sorted data gives O(n) time with O(1) space.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"correctness-proof","title":"Why This Algorithm Is Correct","content":[{"data":{"content":"It's one thing to see that the two-pointer technique works on examples. It's another to understand **why** it's correct—why it doesn't accidentally skip valid solutions.\n\n**Theorem:** For a sorted array, if a valid pair (i, j) exists where i < j and arr[i] + arr[j] = target, the two-pointer algorithm will find it.\n\n**Proof by Invariant:**\n\nThroughout the algorithm, we maintain this invariant:\n\n> *If a solution exists with indices (i, j) where left ≤ i < j ≤ right, then we will find it.*\n\n**Base case:** Initially, left = 0 and right = n-1, so all pairs are potentially in range.\n\n**Inductive step:** Consider what happens at each iteration:"},"type":"text"},{"data":{"type":"ordered","items":["**Case: arr[left] + arr[right] = target** → We found the solution. Done.","**Case: arr[left] + arr[right] < target** → We increment left. Why is this safe? Any pair involving the current left with indices < right would have an even smaller sum (since arr[right] is the largest remaining candidate). So no valid pair uses current left. Safe to eliminate it.","**Case: arr[left] + arr[right] > target** → We decrement right. Why is this safe? Any pair involving current right with indices > left would have an even larger sum (since arr[left] is the smallest remaining candidate). So no valid pair uses current right. Safe to eliminate it."],"title":"Case Analysis for Pointer Movement","variant":"accent"},"type":"list"},{"data":{"content":"**Termination:** The algorithm terminates when left >= right, at which point no valid pairs remain to check.\n\n**Completeness:** Every pair (i, j) with i < j is either:\n- Found (if it's the solution)\n- Eliminated when we advance left past i (because arr[i] was too small with the current right)\n- Eliminated when we retreat right past j (because arr[j] was too large with the current left)\n\nSince every pair is accounted for, the algorithm is correct."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Understanding Proofs Helps Debugging","content":"When your two-pointer implementation has bugs, understanding *why* the algorithm works helps you find them. Common bugs: using <= instead of < in the while condition (causing infinite loops), forgetting to move pointers (causing infinite loops), or moving the wrong pointer based on the condition. The proof tells you exactly what should happen at each step.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"complexity-analysis","title":"Time and Space Complexity","content":[{"data":{"content":"Understanding the complexity of two-pointer algorithms requires careful analysis of how the pointers move.\n\n**Time Complexity: O(n)**\n\nThe analysis is straightforward:"},"type":"text"},{"data":{"items":["The `left` pointer starts at 0 and can only increase (never decrease)","The `right` pointer starts at n-1 and can only decrease (never increase)","Each iteration moves at least one pointer","Total possible movements: left moves ≤ n times, right moves ≤ n times","Therefore: total iterations ≤ n"],"title":"Time Analysis","variant":"glass"},"type":"list"},{"data":{"content":"Note that this is **O(n)**, not O(n/2). While each pointer moves at most n/2 positions on average for balanced movements, in the worst case one pointer might stay fixed while the other traverses the entire array.\n\n**Space Complexity: O(1)**\n\nThe algorithm uses only a **constant** amount of extra memory:"},"type":"text"},{"data":{"items":["`left` pointer: 1 integer","`right` pointer: 1 integer","`current_sum` (optional): 1 integer","Total: O(1) space regardless of input size"],"variant":"glass"},"type":"list"},{"data":{"rows":[["Brute Force","O(n²)","O(1)","Simple but doesn't scale"],["Hash Set","O(n)","O(n)","Fast, works on unsorted data, but uses extra space"],["Two-Pointer","O(n)","O(1)","Optimal time and space, but requires sorted input"]],"caption":"Complexity Comparison: Brute Force vs Two-Pointer","headers":["Approach","Time","Space","Trade-offs"]},"type":"table"},{"data":{"icon":"Info","title":"The Sorting Cost","content":"If the input isn't already sorted, you'll pay O(n log n) to sort it first. The total time becomes O(n log n + n) = O(n log n). This is still better than O(n²), but if you only need to check once and the data is unsorted, a hash set approach might be preferable since it's O(n) without requiring sorted data.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"prerequisites","title":"When Can You Use Two Pointers?","content":[{"data":{"content":"Not every problem can be solved with two pointers. The technique requires specific structural properties in the problem. Understanding these prerequisites helps you quickly identify two-pointer opportunities.\n\n**Prerequisites for Opposite-Direction Two-Pointer:**"},"type":"text"},{"data":{"items":["**Ordered or symmetric data** — The data must have some ordering that allows intelligent pointer movement decisions. Sorted arrays are the classic example.","**Monotonic relationship** — Moving a pointer should have a predictable effect on the metric you're optimizing. E.g., moving left forward increases a sum in sorted arrays.","**Pair-wise or two-point queries** — The problem involves finding or checking pairs, or comparing positions from two ends.","**Eliminative decisions** — Each comparison should eliminate a large portion of the search space, not just one candidate."],"title":{"icon":"CheckCircle","text":"Requirements for Converging Pointers","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Prerequisites for Same-Direction Two-Pointer:**"},"type":"text"},{"data":{"items":["**In-place modification** — You're transforming the array while reading it, and need to track read vs. write positions.","**Partitioning or filtering** — You're separating elements based on some condition while maintaining order or grouping.","**Window tracking** — You're tracking a range or segment that expands/contracts from one end.","**Cycle detection** — In linked structures, you're detecting loops by having pointers move at different speeds."],"title":{"icon":"CheckCircle","text":"Requirements for Fast/Slow Pointers","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"AlertCircle","title":"Not a Silver Bullet","content":"Two-pointer doesn't work for all problems! If there's no ordering, no monotonic relationship, or no way for pointer movements to eliminate large chunks of the search space, the technique likely doesn't apply. Trying to force two-pointer on an unsuitable problem leads to incorrect solutions.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"common-mistakes","title":"Common Mistakes and Pitfalls","content":[{"data":{"content":"Even experienced programmers make mistakes with two-pointer algorithms. Here are the most common pitfalls and how to avoid them:"},"type":"text"},{"data":{"items":["**Off-by-one errors:** Using `left <= right` when you should use `left < right`, or vice versa. For pair sums, you typically want `left < right` (strict inequality) since a number can't pair with itself.","**Forgetting to move pointers:** Every branch of your conditional must move at least one pointer, otherwise you get an infinite loop. If `sum == target`, do you return, or do you need to continue searching for more pairs?","**Moving the wrong pointer:** This is the most dangerous bug because it produces wrong answers silently. Always trace through the logic: if the sum is too small, you need a bigger number, so move the pointer at the smaller element.","**Assuming sorted input:** The algorithm requires sorted data. If you're given unsorted input and forget to sort, you'll get wrong answers.","**Not handling duplicates:** If the array has duplicates and you need unique pairs, you must skip duplicate values when moving pointers.","**Edge cases:** Empty array, single element, no valid pair, all elements the same—test these explicitly."],"title":{"icon":"XCircle","text":"Pitfalls to Avoid","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"fileName":"common_bugs.py","languages":[{"code":"# BUG 1: Wrong condition (should be <, not <=)\nwhile left <= right: # Bug: allows left == right\n # ... this could match an element with itself\n\n# FIX: Use strict inequality for pairs\nwhile left < right:\n # ... correct\n\n# BUG 2: Forgetting to move pointers\nwhile left < right:\n if arr[left] + arr[right] == target:\n print(\"Found!\")\n # Bug: never moves pointers, infinite loop!\n elif current_sum < target:\n left += 1\n else:\n right -= 1\n\n# FIX: Always ensure pointers move\nwhile left < right:\n if arr[left] + arr[right] == target:\n print(\"Found!\")\n return True # Or move both pointers if finding all pairs\n # ...\n\n# BUG 3: Moving wrong pointer\nif current_sum < target:\n right -= 1 # Bug: decreasing sum when it's already too small!\n \n# FIX: Think carefully about direction\nif current_sum < target:\n left += 1 # Correct: move to larger element","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: The Two-Pointer Foundation","content":[{"data":{"content":"You've now established a solid foundation for understanding the two-pointer technique. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Two-pointer is about structured elimination** — Each pointer movement eliminates many candidates, not just one.","**Two main variants exist** — Opposite-direction (converging) for pair problems on sorted data; same-direction (fast/slow) for in-place modifications and partitioning.","**Prerequisites matter** — The technique requires sorted/ordered data and a monotonic relationship between pointer movement and the target metric.","**O(n²) → O(n) transformation** — When applicable, two-pointer converts quadratic brute-force solutions into linear-time algorithms.","**Constant space is a key benefit** — Unlike hash-based approaches, two-pointer uses O(1) extra space.","**Correctness comes from invariants** — Understanding why the algorithm works helps write bug-free code."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nIn the following pages, we'll dive deep into each variant:\n- **Same-direction pointers** (fast and slow): for in-place modifications, removing duplicates, and cycle detection\n- **Opposite-direction pointers** (converging): for pair sums, palindrome checks, and container problems\n- **Classic problems**: the archetypal two-pointer problems that appear repeatedly in interviews\n- **Pattern recognition**: how to identify two-pointer opportunities in novel problems"},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand what the two-pointer technique is, why it works, and when it applies. This conceptual foundation will make the subsequent deep-dives into specific variants and problems much more intuitive.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_593d12981caebe5ec8c4bfe4a75cedf8","title":"Same-Direction Pointers (Fast and Slow)","order":1,"content":null,"isLocked":true},{"id":"seed_61c71d89c8399d9029fbdb1fd6e3c493","title":"Opposite-Direction Pointers (Converging)","order":2,"content":null,"isLocked":true},{"id":"seed_4b5a6f1e06e5d13cf458b74c5b1a8eed","title":"Classic Problems: Pair Sum, Removing Duplicates, Partitioning","order":3,"content":null,"isLocked":true},{"id":"seed_16ecc2a847288c316210ff2fde6ee6b4","title":"When Two-Pointer Applies and When It Doesn't","order":4,"content":null,"isLocked":true}]}}