Arrays & Strings5 min read

Two Pointers

Two fingers tracing an array to solve problems in one pass
time: \(O(n)\)space: \(O(1)\)

Imagine you have a row of numbers, and you need to find a pair that adds up to a specific target. The naive way is to use a nested loop: point your left finger at the first number, then use your right finger to point at every other number. Then move your left finger to the second number, and so on. This takes \(O(n^2)\) time.

The Two Pointers technique is a clever way to do this in just one pass — taking \(O(n)\) time — by moving two variables (pointers) through the array at the same time.

◈ See two pointers move

← → arrow keys to step · click elements to interact

Two Pointer: Pair Sum

def two_sum_sorted(arr, target):
    """Find a pair summing to target in a sorted array."""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return []


print(two_sum_sorted([1, 2, 3, 4, 6], 6))   # [1, 3]  (2+4)
print(two_sum_sorted([2, 7, 11, 15], 9))    # [0, 1]  (2+7)
print(two_sum_sorted([1, 2, 3], 10))        # []  (no pair)
Output
[1, 3]
[0, 1]
[]

Pattern 1: Opposite Ends (Converging Pointers)

This is the most common two-pointer pattern. You place one pointer at the start (left = 0) and one at the end (right = n - 1) of a sorted array.

Say you want to find two numbers that sum to 10 in the array [1, 2, 3, 4, 6, 8, 9]:

  • Look at left (1) + right (9) = 10. Found it!
  • If the sum was too small (e.g., target was 12), you move the left pointer forward to get a bigger number.
  • If the sum was too big (e.g., target was 8), you move the right pointer backward to get a smaller number.

Because the array is sorted, you always know exactly which pointer to move.

Pattern 2: Slow and Fast (Runner Technique)

In this pattern, both pointers start at the same place, but they move at different speeds. The "fast" pointer might move two steps for every one step the "slow" pointer takes.

This is famously used in linked lists to:

  • Find the exact middle: When the fast pointer reaches the end, the slow pointer is perfectly in the middle.
  • Detect cycles: If the fast pointer laps the slow pointer and they meet, there's a loop! (See Floyd's cycle detection.)

Pattern 3: Sliding View (Same Direction)

Sometimes both pointers move at the same speed but stay a fixed distance apart (like a sliding window), or they process elements in-place to remove duplicates (like a sliding window). For example, the fast pointer reads values, and the slow pointer writes them only if they are unique.

Note: Two Pointers usually only works if the array is sorted (for converging pointers) or if you are dealing with a Linked List (for slow/fast pointers). Always check if sorting is allowed first!

Complexity

Time ComplexityEach element is processed at most once
Linear\(O(n)\)
Space ComplexityUses only two integer variables for the pointers
Constant\(O(1)\)

Two Pointer: Remove Duplicates In-Place

def remove_duplicates(arr):
    """Remove duplicates in-place from sorted array. Returns new length."""
    if not arr: return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1


arr = [1, 1, 2, 2, 3, 4, 4, 5]
k = remove_duplicates(arr)
print(arr[:k])  # [1, 2, 3, 4, 5]
print(k)        # 5
Output
[1, 2, 3, 4, 5]
5
Challenge

Quick check

What is the primary requirement for the 'Opposite Ends' two-pointer pattern to work?

Continue reading

Sliding Window
A picture frame scanning over an array to solve sub-array problems in \(O(n)\) time
→
Static Arrays
A row of numbered boxes — fast to grab, fixed in size
→
Singly Linked List
A chain of boxes — each one knows only where the next box is
→