Arrays

Two Pointers

TimeO(n) SpaceO(1)

Imagine two people walking toward each other from opposite ends of a bridge. One starts from the left, one from the right. They each take steps based on what they see, and they meet somewhere in the middle. Together they’ve covered the entire bridge without either one walking the whole thing.

When to use it: The input is sorted (or you can sort it), and you need to find pairs or subarrays satisfying a condition — especially when a brute-force approach would check all pairs in O(n^2).

Key insight: By moving pointers inward based on a comparison, you systematically eliminate impossible pairs without checking them.

Common trap: Forgetting to handle duplicates. When the problem asks for unique pairs, skip over repeated values after finding a match.

# Two-pointer pattern: find a pair that sums to target in a sorted array
function twoSum(arr, target):
    left = 0
    right = length(arr) - 1

    while left < right:
        currentSum = arr[left] + arr[right]

        if currentSum == target:
            return (left, right)        # found the pair
        else if currentSum < target:
            left = left + 1             # need a larger sum
        else:
            right = right - 1           # need a smaller sum

    return null                         # no pair found

# Same-direction two pointers: remove duplicates in-place
function removeDuplicates(arr):
    if length(arr) == 0:
        return 0

    slow = 0                            # write pointer

    for fast = 1 to length(arr) - 1:    # read pointer
        if arr[fast] != arr[slow]:
            slow = slow + 1
            arr[slow] = arr[fast]

    return slow + 1                     # new length

def two_sum_sorted(arr: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1
        else:
            right -= 1

    return None


def remove_duplicates(arr: list[int]) -> int:
    """Remove duplicates in-place from a 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


def three_sum(nums: list[int]) -> list[list[int]]:
    """Find all unique triplets that sum to zero."""
    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:
                left += 1
            elif total > 0:
                right -= 1
            else:
                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

    return result

Problem: Given a sorted array of integers, find two numbers such that they add up to a specific target. Return their indices.

How would you approach this?

Answer: This is a two-pointer problem because the array is sorted and we need a pair summing to a target. Place one pointer at the start and one at the end. If the sum is too small, move the left pointer right; if too large, move the right pointer left.

Problem: Given a sorted array, remove duplicates in-place so that each element appears at most once. Return the new length.

How would you approach this?

Answer: This is a same-direction two-pointer (slow/fast) problem. The slow pointer marks the write position; the fast pointer scans ahead. When fast finds a new value, copy it to slow's position and advance slow.

Time: O(n) because each pointer moves at most n steps total. In the opposite-direction variant, left and right together traverse the array once. In the same-direction variant, the fast pointer scans the entire array while the slow pointer only advances forward.

Space: O(1) because only two index variables are used regardless of input size. The technique modifies data in-place or reads it without extra storage.