Overview

The two pointer technique reduces a brute-force $O(N^2)$ pair search to $O(N)$ by maintaining two indices into an array and moving them toward each other. It applies when the input has some monotonic structure — typically a sorted array — so that moving one pointer provably discards candidates without missing the answer.

In this post I walk through four classic two pointer problems from LeetCode: Two Sum II (167), Trapping Rain Water (42), 3Sum (15), and Remove Duplicates from Sorted Array (26).

167. Two Sum II - Input Array Is Sorted

Problem. Given a sorted array, return the 1-based indices of the two elements that sum to the target.

Approach. Set start to the first index and end to the last, and loop while start < end. Each iteration, compare the sum numbers[start] + numbers[end] with the target:

  • Equal — we found the answer.
  • Greater — since the array is sorted, numbers[end] is the largest value still in range, so decreasing end is the only way to make the sum smaller.
  • Smaller — symmetrically, increasing start is the only way to make the sum larger.

Complexity. $O(N)$ time, where $N$ is the length of the array: every iteration moves exactly one pointer inward, so each element is visited at most once. $O(1)$ space.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        N = len(numbers)
        start = 0
        end = N - 1
        while start < end:
            total = numbers[start] + numbers[end]
            if total == target:
                # converting indices to 1-based
                return [start + 1, end + 1]  
            elif total > target:
                end -= 1
            else:
                start += 1

42. Trapping Rain Water

Problem. Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water is trapped after raining.

Approach. The water above any bar is bounded by the shorter of the tallest wall to its left and the tallest wall to its right:

$$ \texttt{water}[i] = \min(\texttt{left\_max}, \texttt{right\_max}) - \texttt{height}[i] $$

Instead of precomputing both maxima for every position, we walk left and right pointers inward and track left_max and right_max as we go. The key invariant: when $\texttt{height}[\texttt{left}] \le \texttt{height}[\texttt{right}]$, we know $\texttt{right\_max} \ge \texttt{height}[\texttt{right}] \ge \texttt{height}[\texttt{left}]$, so the water level at left is decided by left_max alone — the right side is guaranteed to be at least as tall. That means we can safely process and advance the shorter side:

  • The current bar is taller than that side’s max — it becomes the new max, and no water sits on it.
  • Otherwise — it traps $\texttt{max} - \texttt{height}$ units of water.

Processing the shorter side each step is what makes one pass sufficient; we never need to look ahead.

Complexity. $O(N)$ time: each iteration moves exactly one pointer inward. $O(1)$ space, compared to $O(N)$ for the precomputed prefix/suffix maxima approach.

class Solution:
    def trap(self, height: List[int]) -> int:
        N = len(height)
        left, right = 0, N - 1
        left_max = right_max = 0
        total = 0
        while left < right:
            if height[left] <= height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    total += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    total += right_max - height[right]
                right -= 1
        return total

15. 3Sum

Problem. Given an integer array, return all unique triplets that sum to zero.

Approach. This is Two Sum II wrapped in an outer loop. Sort the array first — that both enables the two pointer search and makes duplicate handling possible. Then fix the smallest element nums[i] and search the remaining subarray nums[i+1:] for a pair summing to -nums[i], exactly as in Two Sum II.

Two extra concerns come from the “unique triplets” requirement:

  • Skip i when nums[i] == nums[i - 1] — a repeated first element would rediscover the same triplets.
  • After recording a match, advance start past any equal values for the same reason.

One more pruning: once nums[i] > 0, every remaining value is positive too (sorted array), so no triplet can sum to zero and we can stop early.

Complexity. $O(N^2)$ time: the outer loop runs $N$ times and each inner two pointer scan is $O(N)$. Sorting adds $O(N \log N)$, which is dominated. $O(1)$ extra space beyond the output.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        N = len(nums)
        result = []
        for i in range(N - 2):
            if nums[i] > 0:
                break
            # skip the duplicated elements
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # while index i is fixed, we find other two indicies 
            # that total sum of three elements is equal to 0
            # by using two pointer algorithm used in Two Sum II

            start, end = i + 1, N - 1
            while start < end:
                total = nums[i] + nums[start] + nums[end]
                if total > 0:
                    end -= 1
                elif total < 0:
                    start += 1
                else:
                    result.append([nums[i], nums[start], nums[end]])
                    start += 1
                    end -= 1
                    # skip the duplicated elements
                    while start < end and nums[start] == nums[start - 1]:
                        start += 1
        return result

26. Remove Duplicates from Sorted Array

Problem. Given a sorted array, remove the duplicates in place so that each value appears once, and return the number of unique elements. The first k slots of the array must hold the unique values in order.

Approach. Unlike the previous problems, the two pointers here move in the same direction — this is the read/write (fast/slow) variant of the pattern:

  • read scans every element from left to right.
  • write marks the next free slot in the deduplicated prefix.

Because the array is sorted, duplicates are adjacent, so nums[read] != nums[read - 1] is enough to detect a new value. When we see one, copy it to nums[write] and advance write. Everything before write is always the deduplicated answer so far, which is why one pass suffices.

Complexity. $O(N)$ time — read visits each element once. $O(1)$ space — the array is rewritten in place.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        write = 1
        for read in range(1, len(nums)):
            if nums[read] != nums[read - 1]:
                nums[write] = nums[read]
                write += 1
        return write

Takeaways

The four problems cover the two main flavors of the technique:

  • Converging pointers (Two Sum II, 3Sum, Trapping Rain Water): start from both ends, and each step use the sorted/monotonic structure to prove that moving one specific pointer cannot skip the answer. The pointer you move is always the one whose side is “settled” — the smaller sum in Two Sum II, the shorter wall in Trapping Rain Water.
  • Read/write pointers (Remove Duplicates): both pointers sweep the same direction, with the slow pointer maintaining an invariant over the prefix — here, “everything before write is deduplicated.” This variant powers most in-place array rewrites.

In both flavors the $O(N)$ bound comes from the same argument: every iteration permanently advances at least one pointer, so no element is ever revisited.