Two Pointers: The Pattern Inside Sorted Array Problems

I've been breaking down coding patterns that took me too long to internalize. The two pointer technique is the one I wish I'd studied first. It shows up in so many problems on LeetCode and in coding interviews that understanding it early would have saved me hours of brute-force attempts.

Why I kept writing nested loops

For months, my approach to array problems was consistent: try every pair with two nested loops. It worked, but it was almost always too slow. The two pointers approach existed everywhere in editorial solutions, but nobody explained the reasoning behind it. Tutorials jumped from "given a sorted array" straight to the answer.

I kept defaulting to brute force and timing out on problems that had O(n) solutions using the two pointer algorithm.

The core idea behind two pointers

The two pointer technique places two index variables at positions in your array and moves them based on conditions. The key insight is that sorting gives you directional guarantees. If your current sum is too small, moving the left pointer right makes it bigger. If too big, moving the right pointer left makes it smaller. You never guess which direction to move.

On an unsorted array, moving a pointer could increase or decrease values unpredictably. Sorting means each pointer movement eliminates an entire set of impossible combinations. That elimination is why two pointers turns O(n²) into O(n).

Two Sum on a sorted array: the foundation

Given a sorted array and target sum, find two numbers that add up to the target.

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

Walk through it with nums = [1, 3, 5, 7, 9] and target = 8. Start with left = 0 (value 1), right = 4 (value 9). Sum is 10, too big. Move right to 3. Now sum is 8. Done in 2 checks instead of 10.

When we moved right from index 4 to 3, we skipped pairs like (3,9) and (5,9). This is safe because the array is sorted. If nums[0] + nums[4] = 10 is too big, then every other pair with nums[4] is also too big since nums[1] >= nums[0]. One move eliminates an entire column of pairs.

Three variations of two pointers

Variation 1: Opposite ends moving inward

This is the Two Sum pattern. Start at both ends, move inward based on comparisons. Container With Most Water uses this approach. You maximize the area between two heights by always moving the pointer at the shorter height.

def max_area(height):
    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
        else:
            right -= 1
    return best

Variation 2: Fast and slow pointers

Both pointers start at the beginning. One moves faster. This is Floyd's cycle detection algorithm applied to arrays. Remove Duplicates from a Sorted Array demonstrates it clearly.

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

The slow pointer advances only when a new unique value appears. The fast pointer scans ahead continuously. Their divergence tracks exactly how many duplicates exist.

Variation 3: Expanding from center

Start both pointers at one position and expand outward. This is the standard approach for palindrome two pointers problems.

def longest_palindrome(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    result = ""
    for i in range(len(s)):
        odd = expand(i, i)
        even = expand(i, i + 1)
        result = max(result, odd, even, key=len)
    
    return result

Each center expansion takes O(n) worst case across n centers, giving O(n²) total. Still much better than O(n³) brute force checking every substring.

Two pointers vs sliding window

These two patterns both use two indices and avoid nested loops, but the intent differs. Two pointers works on sorted data with pointer movement driven by value comparisons. Sliding window maintains a contiguous subarray satisfying some property on sequential data.

Sliding window is technically a special case of two pointers where both move in the same direction and the gap represents a contiguous subarray. But the problem-solving approach differs. Sorted array with pairs means two pointers. Contiguous subarrays maintaining a property means sliding window.

I wrote about the sliding window pattern in detail here. The two patterns complement each other by covering different shapes of the same optimization.

3Sum with two pointers: a full walkthrough

3Sum is the problem that turns the two pointer technique into an interview favorite. Given an array, find every unique triplet that sums to zero. Sort the array first, fix one number, then run two pointers across the rest of the array to find pairs that complete the triplet.

Walk through nums = [-4, -1, -1, 0, 1, 2]. After sorting, fix the leftmost value and place a left pointer just after it and a right pointer at the end. When the sum of the three values is too small, move the left pointer right to increase it. When the sum is too large, move the right pointer left to decrease it. When the sum equals zero, record the triplet and move both pointers inward, skipping duplicate values so each triplet is counted once. The outer loop fixes each anchor in turn, so the whole scan runs in O(n squared) time.

def three_sum_scan(nums, i):
    # inner two-pointer sweep for a fixed anchor nums[i]
    left, right = i + 1, len(nums) - 1
    found = []
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total < 0:
            left += 1          # sum too small, grow it
        elif total > 0:
            right -= 1         # sum too large, shrink it
        else:
            found.append((nums[i], nums[left], nums[right]))
            left += 1
            right -= 1
            while left < right and nums[left] == nums[left - 1]:
                left += 1      # skip duplicate left values
    return found

Reorder the Array: the same trick in competitive programming (CF 1007A)

Competitive programming leans on the same sorted two pointer sweep. Codeforces 1007A, Reorder the Array, asks for the maximum number of positions where a rearranged value is strictly greater than the original value. The trick is to sort the array and then greedily match values with two pointers.

Sort the values ascending. Use one pointer to scan candidate values you want to place and a second pointer to choose which sorted value you are trying to beat. Advance the candidate pointer until it finds a value strictly greater than the current target, count a match, then move both pointers forward. If the candidate cannot beat the target, skip that target. The sort costs O(n log n) and the matching sweep is a single O(n) pass, so the same pattern that solves 3Sum also solves this contest problem.

def max_greater_positions(a):
    a.sort()
    place = 0            # pointer over candidate values
    count = 0
    for target in a:     # pointer over values to beat
        while place < len(a) and a[place] <= target:
            place += 1   # advance until a candidate beats target
        if place < len(a):
            count += 1
            place += 1
    return count

The same greedy two pointer editorial shows up for Codeforces 1008C and other reorder-style contest problems, so recognizing it once pays off across both interview and competitive programming settings.

Two pointers on linked lists

The two pointer technique is not limited to arrays. On a linked list you cannot index positions, but you can still run two references at different speeds or offsets. A fast pointer that moves two nodes per step while a slow pointer moves one lands the slow pointer at the middle when the fast pointer reaches the end. Offset the two pointers by k nodes and the trailing pointer sits on the kth node from the end when the leading pointer finishes, which is exactly how you remove the nth node from the end in a single pass. The same fast and slow idea powers Floyd's cycle detection: if the two pointers ever meet, the list has a cycle. Because a linked list has no random access, these pointer tricks replace the O(n) space you would otherwise spend copying nodes into an array. I broke down remove nth node, palindrome checks, and list reordering in a dedicated two pointers on linked lists guide. The mental model is identical to the sorted array case: two references, moved on a rule.

Common mistakes with two pointers

Forgetting to sort first is the most common error. The two pointer technique depends on sorted order for directional guarantees. On unsorted data, pointer movements become unpredictable.

Not handling duplicates causes bugs in problems like 3Sum. After finding a valid triplet, advance both pointers past duplicate values.

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]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

Using two pointers when a hash map is simpler wastes effort. For unsorted Two Sum where you need indices, a hash map gives O(n) without sorting. The two pointer approach works best when data is already sorted or sorting preserves the needed information.

How to identify two pointer problems

Look for these signals in problem statements: the array is sorted or can be sorted without losing information. You need pairs, triplets, or subsequences satisfying a condition. Brute force requires nested loops. Moving one pointer consistently increases or decreases a relevant value.

Practice problems for two pointers

Two Sum II (sorted input) is the foundational two pointers LeetCode problem. Explain why each pointer movement is safe to confirm understanding.

3Sum extends the two pointer technique with an outer loop. Duplicate handling is the challenge, not the pointer logic.

Container With Most Water tests the elimination argument outside a typical "find a pair" context.

Remove Duplicates from Sorted Array is the cleanest fast/slow pointer problem.

Longest Palindromic Substring practices center expansion.

Trapping Rain Water combines the two pointer algorithm with extra bookkeeping. The core logic is the same opposite-ends pattern.

After those, try the problems on Levelop's coding patterns track. That's where I worked through these variations and started seeing the connections.