beginnerintermediateadvanced

Data Structures & Algorithms · Section 6

Two Pointers

Level: beginner
Read: 60 min
Concepts: 6

The three shapes two pointers take — opposite ends converging, same direction at different speeds, and one-per-structure for a merge — plus the three-pointer extension (3Sum) and the sorted-input signal that tells you to reach for this pattern.

What is true here

On a sorted array, opposite-direction pointers turn a pair-sum search into an O(n) scan with no hash map.
Same-direction fast/slow pointers compact or filter an array in place, in one pass, with O(1) extra space.
Fast/slow pointers at different SPEEDS (Floyd's algorithm) detect a cycle in a linked structure without a visited set.
A sorted array or list, plus a request for a pair or triplet, is the standard signal to reach for two pointers first.

What you will be able to do

Find a pair with a target sum in a sorted array in O(n) time and O(1) space
Compact or filter an array in place using slow/fast pointers moving in the same direction
Detect a cycle in a linked structure using Floyd's fast/slow pointer algorithm
Recognize a sorted-input pair/triplet problem as a two-pointer problem before reaching for anything heavier

Concepts

The three pointer shapes, what each is for, and the signal that tells you which one applies.

Opposite-direction pointers (start/end converging)

corebeginner

Two pointers start at the two ends of a sorted array or string and move toward each other, comparing or combining the elements they point at — reversing, checking a palindrome, or finding a pair with a target sum, all in one O(n) pass.

Think of it as

left starts at index 0, right starts at the last index. Each step looks at both elements together, decides what to do, and moves at least one pointer inward, shrinking the gap between them. The moment left and right meet or cross, every relevant pair has already been considered exactly once.

What we're doing: Find two numbers in a SORTED array that add up to a target, without a hash map.

two_sum_sorted.pypython

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1
    return []


print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 2, 3, 4, 6], 6))

5: Because the array is sorted, a total that is too small can ONLY be fixed by moving left inward — every value at or before it is even smaller.
7: Symmetrically, a total that is too big can only be fixed by moving right inward.

Output

[0, 1]
[1, 3]

Why this works: For [2, 7, 11, 15], target 9: starting at 2 + 15 = 17 (too big, move right), then 2 + 11 = 13 (too big, move right), then 2 + 7 = 9 — a match at indices [0, 1]. The second call similarly narrows down to indices 1 and 3 (2 + 4 = 6).

Moving the wrong pointer when the sum misses the target

Wrong

python

def two_sum_sorted_wrong(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total < target:
            right -= 1
        else:
            left += 1
    return []


print(two_sum_sorted_wrong([2, 7, 11, 15], 9))

Better

python

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

What you see: two_sum_sorted_wrong([2, 7, 11, 15], 9) returns [] even though 2 + 7 = 9 is a valid answer at indices 0 and 1.

Why: The branches are swapped: a sum that is too big moves right further down (making it even smaller than needed) instead of moving right inward correctly, and there is no equality check at all — the pointers end up sliding past the answer without ever comparing to it.

Two Sum II - Input Array Is SortedeasyLeetCode
Exactly the example above — the sorted-array version of Two Sum, in O(1) space instead of a hash map.
Container With Most WatermediumLeetCode
Start at both ends; always move the pointer at the SHORTER line inward, since the taller one can never be the bottleneck again.

Remember: On a sorted array: sum too small, move left inward; sum too big, move right inward — swapping that rule breaks the search entirely.

Was this helpful?

Same-direction pointers (fast/slow at different rates)

corebeginner

Two pointers both move forward through the same array — slow marks where the next kept value goes, fast scans ahead looking for one — letting you filter or compact an array in place, in one pass, with no second array.

Think of it as

slow points at the boundary of what has been kept so far. fast scans forward one step at a time, checking each candidate. When fast finds something worth keeping, it gets written just past slow, and slow advances to that new position. By the end, everything from index 0 up to slow is the compacted answer.

What we're doing: Remove duplicates from a SORTED array in place, returning the count of unique values.

remove_duplicates.pypython

def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1


nums = [1, 1, 2, 2, 2, 3]
k = remove_duplicates(nums)
print(k, nums[:k])

5: nums[fast] is compared against nums[slow] — the last value actually KEPT, not just the previous scanned position.
7: slow only advances, and nums is only overwritten, when fast finds a genuinely new value.

Output

3 [1, 2, 3]

Why this works: [1, 1, 2, 2, 2, 3] has three unique values. slow ends at index 2 after writing 1, 2, and 3 into the front of the array — nums[:3] confirms the compacted result, and the 3 duplicate 1s/2s beyond it are ignored.

Running this exact technique on an array that is not sorted

Wrong

python

nums = [1, 2, 1, 3, 2]  # NOT sorted
print(remove_duplicates(nums), nums[:5])

Better

python

nums = [1, 2, 1, 3, 2]
nums.sort()
k = remove_duplicates(nums)
print(k, nums[:k])

What you see: remove_duplicates([1, 2, 1, 3, 2]) returns 5, claiming every element is unique — even though 1 and 2 each appear twice.

Why: The technique only compares each element to the immediately PRECEDING one, which correctly catches duplicates only when they are adjacent — guaranteed on a sorted array, not otherwise. Sorting first (or using a set-based approach instead) is required whenever the input is not already sorted.

Remove Duplicates from Sorted ArrayeasyLeetCode
Exactly the example above — slow marks the write position, fast scans for the next new value.
Move ZeroeseasyLeetCode
slow marks where the next non-zero value goes; fast scans for one. Fill everything after slow with zeroes at the end.

Remember: slow marks the last kept value, fast scans ahead — but this pattern only removes duplicates correctly when equal values are adjacent, which a sorted array guarantees and an unsorted one does not.

Was this helpful?

Fast/slow pointers for cycle detection (Floyd's algorithm)

corebeginner

Two pointers walk the same linked structure at different speeds — slow moves one step, fast moves two. If there is a cycle, fast eventually laps slow and they land on the same node; if there is no cycle, fast simply reaches the end first.

Think of it as

Picture two runners on a track. If the track loops back on itself, the faster runner is guaranteed to catch up to the slower one from behind eventually. If the track is a straight line with an end, the faster runner just reaches that end and stops — the two can never meet.

What we're doing: Detect whether a linked list contains a cycle, using O(1) extra space.

has_cycle.pypython

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


a = Node(1)
b = Node(2)
c = Node(3)
a.next, b.next, c.next = b, c, None
print(has_cycle(a))

c.next = a  # introduces a cycle back to the head
print(has_cycle(a))

9: fast and fast.next both have to be truthy — fast needs a next node, and that next node needs to exist too, before jumping two steps ahead.
11: slow is fast checks object identity, not value equality — two different nodes could coincidentally hold the same value.

Output

False
True

Why this works: The first list (a -> b -> c -> None) has no cycle, so fast reaches None and the loop ends with False. After c.next = a rewires the list into a loop, fast eventually laps slow and they land on the same node, returning True.

Checking only `while fast`, without also checking `fast.next`

Wrong

python

def has_cycle_wrong(head):
    slow = fast = head
    while fast:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Better

python

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

What you see: has_cycle_wrong on a non-cyclic 3-node list (a -> b -> c -> None) raises AttributeError: 'NoneType' object has no attribute 'next'.

Why: Once fast lands on the LAST node, fast.next is None — fast is still truthy, so the loop body runs again and tries None.next, which does not exist. Checking fast.next in the loop condition stops one step earlier, before that crash.

Linked List CycleeasyLeetCode
Exactly the example above — return True the moment slow and fast land on the same node.
Find the Duplicate NumbermediumLeetCode
Treat the array's values as 'next pointers' (index i points to index nums[i]) — the duplicate creates a cycle that Floyd's algorithm finds in O(1) space.

Remember: fast moves two, slow moves one; check `fast and fast.next` before advancing fast, or a non-cyclic list crashes on None.next.

Merging two sorted structures with two pointers

standardbeginner

To merge two already-sorted sequences into one sorted sequence, walk both with one pointer each and always take the smaller of the two current elements — O(n + m) total, with no re-sorting.

Think of it as

i tracks a position in the first sequence, j in the second. At each step, compare the elements i and j currently point at, and append whichever is smaller, advancing only that one pointer. The moment either sequence runs out, everything left in the other is already sorted, so it can be appended directly with no more comparisons.

What we're doing: Merge two sorted lists into one sorted list using one pointer per list.

merge_sorted.pypython

def merge_sorted(a, b):
    i = j = 0
    merged = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            merged.append(a[i])
            i += 1
        else:
            merged.append(b[j])
            j += 1
    merged.extend(a[i:])
    merged.extend(b[j:])
    return merged


print(merge_sorted([1, 3, 5], [2, 4, 6, 8]))

4: The loop only runs while BOTH lists still have unread elements.
8: merged.extend(a[i:]) and merged.extend(b[j:]) tack on whatever is left — at most one of these does anything.

Output

[1, 2, 3, 4, 5, 6, 8]

Why this works: i and j interleave 1, 2, 3, 4, 5 by always taking the smaller front value; once a runs out after 5, the remaining [6, 8] from b is appended directly, since it is already sorted.

Merge Sorted ArrayeasyLeetCode
The in-place variant of the example above — merging from the BACK avoids overwriting values not yet read.
Merge k Sorted ListshardLeetCode
The same two-pointer merge, generalized: merge lists two at a time, or use a heap to pick the smallest front across all k at once.

Remember: Two pointers, one per sorted sequence, always advancing the one pointing at the smaller value — merging never needs to re-sort or compare against more than the two current fronts.

Was this helpful?

Three pointers (e.g. 3Sum built on top of two pointers)

standardbeginner

Fix one element with a loop, then run the opposite-direction two-pointer scan on everything after it — turning a 3-variable search into a 1-variable loop wrapped around a 2-pointer scan.

Think of it as

Sort the array first. For each index i, treat everything after it as its own two-pointer subproblem: find a left/right pair whose sum, together with nums[i], hits the target. Skipping past a value equal to the one just tried — at i, at left, and at right — is what keeps the same triplet from being recorded more than once.

What we're doing: Find every unique triplet in an array that sums to zero.

three_sum.pypython

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result


print(three_sum([-1, 0, 1, 2, -1, -4]))

4: i only needs to reach len(nums) - 2 — left and right always need at least two elements after it.
5: Skipping a repeated nums[i] stops the same fixed value from producing the same set of triplets twice.
7: left and right run the exact opposite-direction two-pointer scan on nums[i+1:], just like Two Sum on a sorted array.

Output

[[-1, -1, 2], [-1, 0, 1]]

Why this works: Sorted, the array is [-4, -1, -1, 0, 1, 2]. Fixing i at the first -1 finds the pair (-1, 2); fixing i at the next -1 is skipped as a repeat of the first, but the two-pointer scan for THAT i still finds a different valid pair (0, 1) before i moves on — giving exactly two unique triplets.

Two Sum II - Input Array Is SortedeasyLeetCode
The inner two-pointer scan this pattern is built on — solve it alone first.
3SummediumLeetCode
Exactly the example above — sort, fix one index, two-pointer the rest, skip repeats at all three positions.

Remember: One fixed index plus a two-pointer scan on the rest turns 3Sum into the same O(n) inner pattern as Two Sum on a sorted array — sort first, and skip repeats at every one of the three positions.

Was this helpful?

Recognizing when a problem on a sorted array/list is a two-pointer problem in disguise

referencebeginner

Whenever a problem gives a SORTED array or list and asks for a pair, triplet, or relationship between elements, try two pointers before anything more complex — sortedness is what lets pointer movement replace a nested loop.

Remember: Sorted + pair/triplet is the two-pointer signal — but only sort first if the answer needs VALUES, not original positions.

Was this helpful?

Spotted a mistake on this page? Tell us.

Read Sheet