The Two Pointer Technique: A Complete Guide

The two pointer technique reduces brute force O(n^2) solutions to O(n) by using two indices that move through a data structure in a coordinated way. If you are preparing for technical interviews, this is one of the first patterns you should internalize.

When to Use Two Pointers

Two pointers work best when the problem involves a sorted array or linked list and you need to find pairs, triplets, or subarrays that satisfy some condition. The key signal is that a naive approach would require nested loops over the same data. If sorting the input first does not break the problem, two pointers can almost always replace that nested loop.

Look for these clues: "find a pair that sums to X," "remove duplicates in place," "determine if a string is a palindrome," or "merge two sorted arrays."

The Three Main Variations

Opposite-End Pointers

Place one pointer at the start and one at the end. Move them inward based on a condition. In Two Sum II (Input Array Is Sorted), if the sum is too small, increment left. If too large, decrement right. Each step eliminates possibilities, giving you O(n) instead of O(n^2).

Container With Most Water uses the same pattern -- you always move the pointer with the shorter height because moving the taller one can never increase the area.

Example: Two Sum II - Input Array Is Sorted Given a 1-indexed sorted array of integers, find two numbers that add up to a specific target. The solution uses opposite-end pointers to find the pair in O(n) time.

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            # Return 1-indexed positions
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]  # No solution found

Same-Direction Pointers (Fast and Slow)

Both pointers start at the same position but move at different speeds. The classic use case is cycle detection in a linked list: slow moves one step, fast moves two. If they meet, there is a cycle.

This pattern also handles in-place array modifications. In Remove Duplicates from Sorted Array, the slow pointer marks the position of the next unique element while the fast pointer scans ahead.

The same-direction approach powers the "find middle of linked list" trick -- when the fast pointer reaches the end, the slow pointer is at the middle.

Example: Remove Duplicates from Sorted Array Given a sorted array, remove duplicates in-place such that each unique element appears only once. Return the new length. The fast pointer (j) explores the array, while the slow pointer (i) tracks the position of the last unique element.

def removeDuplicates(nums):
    if not nums:
        return 0
    i = 0  # Slow pointer
    for j in range(1, len(nums)):  # Fast pointer
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1  # Length of unique elements

Sliding Window (A Close Relative)

Sliding window is a variant where both pointers move in the same direction and define a range. The key difference: two pointers search for specific elements, while sliding window maintains a valid subarray or substring. We cover this in a separate article.

Common Techniques

Sorting first. Three Sum sorts the array, fixes one element, then runs opposite-end pointers on the rest. If the problem does not say the input is sorted, consider whether sorting changes the answer.

Skipping duplicates. When the problem asks for unique results (like Three Sum returning unique triplets), skip duplicate values as you advance pointers past identical values.

Multiple passes. Trapping Rain Water can be solved with two passes (prefix max from left, suffix max from right) or with opposite-end pointers in a single pass.

Example: Three Sum Find all unique triplets in an array that sum to zero. The solution involves sorting the array, then for each element, using opposite-end pointers to find pairs that sum to the negative of that element. Duplicate skipping is crucial.

def threeSum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Skip duplicate starting elements
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        target = -nums[i]

        while left < right:
            current_sum = nums[left] + nums[right]
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                # Skip duplicates for left and right pointers
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    return result

Complexity

Two pointer solutions run in O(n) time for a single pass, or O(n log n) when sorting is required. Space complexity is typically O(1) for in-place operations, though some problems like Three Sum require O(k) space for storing results (where k is the number of valid combinations).

Time Complexity Breakdown:

• Opposite-End Pointers: O(n) for a single pass through the array
• Same-Direction Pointers: O(n) for a single traversal
• With Sorting: O(n log n) for the sort plus O(n) for pointer operations = O(n log n) overall

Space Complexity:

• Most two pointer solutions use O(1) extra space
• Exceptions include problems that require storing results (like Three Sum) or recursive implementations

Practice Problems

1. Valid Palindrome -- Basic opposite-end check. Check if a string reads the same forward and backward, ignoring non-alphanumeric characters and case.

2. Two Sum II (Input Array Is Sorted) -- Classic opposite-end pair finding. As shown in the example above.

3. Remove Duplicates from Sorted Array -- Same-direction pointer for in-place modification. As shown in the example above.

4. Three Sum -- Sorting, fixing one element, and running two pointers. Practice skipping duplicates. As shown in the example above.

5. Container With Most Water -- Opposite-end with a greedy argument for which pointer to move. Given an array of heights, find two lines that together with the x-axis form a container that holds the most water.

6. Trapping Rain Water -- Try both the prefix/suffix approach and the two pointer O(1) space approach. Given an elevation map, compute how much water it can trap after raining.

Example: Container With Most Water This problem demonstrates the greedy nature of opposite-end pointers. You always move the pointer with the smaller height, as moving the taller pointer cannot possibly increase the area.

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # Calculate current area
        width = right - left
        current_height = min(height[left], height[right])
        current_area = width * current_height
        max_area = max(max_area, current_area)

        # Move the pointer with smaller height
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

Find related problems organized by company on the CodeJeet dashboard. Companies like Google and Amazon frequently test two pointer variations.

When you see a problem involving arrays, strings, or linked lists, ask yourself: "Can I solve this with two indices instead of nested loops?" Drill the three variations until they feel automatic, and you will recognize the pattern within seconds during an interview.

Advanced Applications and Edge Cases

Linked List Problems: The fast and slow pointer technique is essential for linked list problems beyond cycle detection. It can be used to find the middle node, detect palindromes in linked lists, or find the kth node from the end.

String Manipulation: Two pointers are frequently used in string problems for tasks like comparing strings with backspaces, checking subsequences, or compressing strings in-place.

Multiple Pointer Variations: Some problems require more than two pointers. For example, the Four Sum problem can be solved by extending the Three Sum approach with an additional outer loop.

Non-Sorted Arrays: While two pointers typically work best with sorted data, some problems with unsorted arrays can still benefit from this technique when combined with other data structures like hash maps.

Memory-Efficient Solutions: Two pointer techniques often provide the most memory-efficient solutions, making them ideal for environments with strict memory constraints or when working with very large datasets.