What is the Two-Pointer Technique - The Two-Pointer Technique | OneNoughtOne

0/361

Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

1 / 5

What is the Two-Pointer Technique

The Pattern That Transforms Quadratic into Linear

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.

What You Will Learn

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.

The Core Concept

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.

The fundamental insight:

In many problems, the brute-force approach examines pairs (or subsequences) that can be logically eliminated. The two-pointer technique exploits this by:

Starting from strategic positions (e.g., both ends of an array, or both at the beginning)
Moving based on comparison outcomes (e.g., if the sum is too small, move one pointer to increase it)
Guaranteeing completeness (every valid solution is considered, even if most are skipped)

This is not a heuristic or approximation—when applicable, the two-pointer technique gives correct answers in optimal time.

A Pointer Is Just an Index

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.

Visualizing the technique:

Consider 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.

Array:  [1,  3,  5,  7,  9]
         ↑               ↑
       left           right
      (value=1)      (value=9)

Now, each pointer can move inward. If we're searching for a target sum:

If the current sum is too small, we need a larger value → move left right
If the current sum is too large, we need a smaller value → move right left
If we've found the target, we're done

Each 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.

Why Two Pointers Work

The two-pointer technique works because of a crucial property: each pointer movement logically eliminates multiple possibilities.

Let's prove this with the two-sum problem on a sorted array. Given [1, 3, 5, 7, 9] with target 10:

Two-Pointer Walk-Through: Finding Two Numbers That Sum to 10
Step	Left Index	Right Index	Left Value	Right Value	Sum	Action
1	0	4	1	9	10	Found! (1 + 9 = 10)

In this case, we got lucky and found the answer immediately. But let's try target 8:

Two-Pointer Walk-Through: Finding Two Numbers That Sum to 8
Step	Left Index	Right Index	Left Value	Right Value	Sum	Action
1	0	4	1	9	10	Too large → move right left
2	0	3	1	7	8	Found! (1 + 7 = 8)

Why moving right left was correct:

When 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.

This is the secret sauce: one comparison eliminates an entire row or column of the pair matrix.

The Pair Matrix Mental Model

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.

The invariant that makes it work:

Throughout 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.

When we move left right, we're saying "all pairs involving the old left index have been handled." When we move right left, we're saying "all pairs involving the old right index have been handled."

At termination, every pair has been considered—most were eliminated without explicit examination, but the logic guarantees they weren't valid solutions.

The Two Fundamental Variants

Two-pointer techniques come in two primary flavors, each suited to different problem types:

Opposite-Direction (Converging)

•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

Same-Direction (Fast & Slow)

•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

When to use which variant:

Problem Characteristic	Suggested Variant
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

The choice isn't always obvious, but pattern recognition comes quickly with practice.

The Brute-Force to Two-Pointer Transformation

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.

Problem: Given a sorted array, find if there exist two elements whose sum equals a target value.

two_pointer_two_sum.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def has_pair_with_sum(arr: list[int], target: int) -> bool:
    """
    Two-pointer approach: Exploit sorted order.
    Time: O(n) - single pass with two pointers
    Space: O(1) - only two index variables
    
    Key insight: In a sorted array, moving left pointer
    increases the sum, moving right pointer decreases it.
    """
    left = 0
    right = len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return True  # Found the pair
        elif current_sum < target:
            # Sum too small, need larger values
            left += 1
        else:
            # Sum too large, need smaller values
            right -= 1
    
    return False  # Pointers crossed, no pair found
 
# Example usage
arr = [1, 3, 5, 7, 9]
print(has_pair_with_sum(arr, 8))   # True (1 + 7)
print(has_pair_with_sum(arr, 20))  # False

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.

Prerequisite: Sorted Data

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.

Why This Algorithm Is Correct

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.

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.

Proof by Invariant:

Throughout the algorithm, we maintain this invariant:

If a solution exists with indices (i, j) where left ≤ i < j ≤ right, then we will find it.

Base case: Initially, left = 0 and right = n-1, so all pairs are potentially in range.

Inductive step: Consider what happens at each iteration:

Case Analysis for Pointer Movement

•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.

Termination: The algorithm terminates when left >= right, at which point no valid pairs remain to check.

Completeness: Every pair (i, j) with i < j is either:

Found (if it's the solution)
Eliminated when we advance left past i (because arr[i] was too small with the current right)
Eliminated when we retreat right past j (because arr[j] was too large with the current left)

Since every pair is accounted for, the algorithm is correct.

Understanding Proofs Helps Debugging

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.

Time and Space Complexity

Understanding the complexity of two-pointer algorithms requires careful analysis of how the pointers move.

Time Complexity: O(n)

The analysis is straightforward:

Time Analysis

•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

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.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra memory:

•left pointer: 1 integer
•right pointer: 1 integer
•current_sum (optional): 1 integer
•Total: O(1) space regardless of input size

Complexity Comparison: Brute Force vs Two-Pointer
Approach	Time	Space	Trade-offs
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

The Sorting Cost

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.

When Can You Use Two Pointers?

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.

Prerequisites for Opposite-Direction Two-Pointer:

Requirements for Converging Pointers

•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.

Prerequisites for Same-Direction Two-Pointer:

Requirements for Fast/Slow Pointers

•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.

Not a Silver Bullet

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.

Common Mistakes and Pitfalls

Even experienced programmers make mistakes with two-pointer algorithms. Here are the most common pitfalls and how to avoid them:

Pitfalls to Avoid

•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.

common_bugs.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# BUG 1: Wrong condition (should be <, not <=)
while left <= right:  # Bug: allows left == right
    # ... this could match an element with itself
 
# FIX: Use strict inequality for pairs
while left < right:
    # ... correct
 
# BUG 2: Forgetting to move pointers
while left < right:
    if arr[left] + arr[right] == target:
        print("Found!")
        # Bug: never moves pointers, infinite loop!
    elif current_sum < target:
        left += 1
    else:
        right -= 1
 
# FIX: Always ensure pointers move
while left < right:
    if arr[left] + arr[right] == target:
        print("Found!")
        return True  # Or move both pointers if finding all pairs
    # ...
 
# BUG 3: Moving wrong pointer
if current_sum < target:
    right -= 1  # Bug: decreasing sum when it's already too small!
    
# FIX: Think carefully about direction
if current_sum < target:
    left += 1  # Correct: move to larger element

Summary: The Two-Pointer Foundation

You've now established a solid foundation for understanding the two-pointer technique. Let's consolidate the key insights:

Key Takeaways

•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.

What's next:

In the following pages, we'll dive deep into each variant:

Same-direction pointers (fast and slow): for in-place modifications, removing duplicates, and cycle detection
Opposite-direction pointers (converging): for pair sums, palindrome checks, and container problems
Classic problems: the archetypal two-pointer problems that appear repeatedly in interviews
Pattern recognition: how to identify two-pointer opportunities in novel problems

Page Complete

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.