Two Pointers Technique: Every Pattern and Problem Explained

Two pointers is less a single technique than a family of them. "Use two pointers" can mean walking inward from both ends of a sorted array, compacting an array in place, racing a fast pointer against a slow one through a linked list, or partitioning around a pivot. They share an idea, using a second index so a single pass does the work of a nested loop, but the invariants and failure modes are different for each.

This guide treats each family separately: the invariant that makes it correct, a template, two or three representative problems with Python and Java code, and the bugs that show up in interviews. The proofs are short, and they matter. "Why can you move the left pointer here?" is the most common follow-up on these problems.

The Five Families of Two Pointer Problems

The sliding window technique is a sixth relative: same-direction pointers where you also maintain state about everything between them. It's covered separately because it has its own templates.

Opposite-End Pointers: Pair Problems on Sorted Arrays

Two Sum II, Input Array Is Sorted (LeetCode 167)

Given a sorted array, find two numbers that add to target. Put lo at the start and hi at the end. If the sum is too small, move lo right; if it's too big, move hi left.

def twoSum(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]      # problem uses 1-based indices
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

public int[] twoSum(int[] numbers, int target) {
    int lo = 0, hi = numbers.length - 1;
    while (lo < hi) {
        int s = numbers[lo] + numbers[hi];
        if (s == target) return new int[]{lo + 1, hi + 1};
        if (s < target) lo++;
        else hi--;
    }
    return new int[0];
}

Why it's correct. Picture an n×n grid where cell (i, j) holds numbers[i] + numbers[j]. Rows increase left to right, columns increase top to bottom. If numbers[lo] + numbers[hi] < target, then pairing lo with any index below hi gives an even smaller sum, so the whole row lo is useless and we discard it with lo++. Symmetrically, a too-large sum kills column hi. Each step eliminates a full row or column, so after at most n steps we've either found the pair or exhausted the grid. O(n) time, O(1) space, versus O(n) space for the hash map approach in the original Two Sum.

Squares of a Sorted Array (LeetCode 977)

The input is sorted but may contain negatives, so squares are largest at the two ends and smallest somewhere in the middle. Compare the ends and fill the output from the back.

def sortedSquares(nums):
    n = len(nums)
    res = [0] * n
    lo, hi = 0, n - 1
    for pos in range(n - 1, -1, -1):
        if abs(nums[lo]) > abs(nums[hi]):
            res[pos] = nums[lo] * nums[lo]
            lo += 1
        else:
            res[pos] = nums[hi] * nums[hi]
            hi -= 1
    return res

That's O(n) instead of the O(n log n) "square then sort". Filling from the back is a recurring move: whenever the extremes are easy to identify and the middle isn't, build the answer from the extremes.

Container With Most Water (LeetCode 11)

Area between lines lo and hi is (hi − lo) × min(h[lo], h[hi]). Start with the widest container and always move the shorter line inward.

public int maxArea(int[] h) {
    int lo = 0, hi = h.length - 1, best = 0;
    while (lo < hi) {
        best = Math.max(best, (hi - lo) * Math.min(h[lo], h[hi]));
        if (h[lo] < h[hi]) lo++;
        else hi--;
    }
    return best;
}

Why moving the shorter line is safe: suppose h[lo] ≤ h[hi]. Any container using lo with some other right end j < hi has smaller width, and its height is still capped by h[lo]. So every remaining container that uses lo is no better than the one we just measured, and we can discard lo. Moving the taller line instead could only make things worse. The LeetCode 11 explainer walks through this with a diagram.

Valid Palindrome (LeetCode 125) and the "skip junk" variant

def isPalindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if not s[lo].isalnum():
            lo += 1
        elif not s[hi].isalnum():
            hi -= 1
        elif s[lo].lower() != s[hi].lower():
            return False
        else:
            lo += 1
            hi -= 1
    return True

The follow-up, Valid Palindrome II (680), allows deleting one character. On the first mismatch, check whether either s[lo+1..hi] or s[lo..hi−1] is a palindrome. That's still O(n) because you branch only once.

Trapping Rain Water (42) is also an opposite-ends problem: whichever side has the smaller running maximum determines the water level on that side, so you process that side and move it inward. It deserves its own page, and has one: trapping rain water explained.

Read/Write Pointers: In-Place Array Compaction

Here read scans every element and write marks where the next kept element goes. The invariant: everything before write is the finished answer. Because write never overtakes read, you never overwrite an element you haven't looked at yet.

Remove Duplicates from Sorted Array (26) and the "at most k copies" generalisation (80)

def removeDuplicates(nums, k=1):
    write = 0
    for x in nums:
        # keep x if fewer than k kept so far, or it differs from
        # the element k positions back in the kept prefix
        if write < k or x != nums[write - k]:
            nums[write] = x
            write += 1
    return write

# k=1 solves LeetCode 26, k=2 solves LeetCode 80

public int removeDuplicates(int[] nums, int k) {
    int write = 0;
    for (int x : nums) {
        if (write < k || x != nums[write - k]) {
            nums[write++] = x;
        }
    }
    return write;
}

Comparing against nums[write − k] rather than nums[read − k] is the key detail. The kept prefix is what matters; the original positions have been partially overwritten. Dry run with k = 2 on [1,1,1,2,2,3]: keep 1, keep 1, skip the third 1 (equals nums[0]), keep 2, keep 2, keep 3. Result length 5: [1,1,2,2,3].

Move Zeroes (LeetCode 283)

def moveZeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

Swapping instead of overwriting keeps the zeros at the end automatically and preserves the relative order of non-zero elements. It's stable for the non-zeros, which is what the problem demands. The same skeleton handles Remove Element (27) and "segregate even and odd" questions.

Fast and Slow Pointers (Floyd's Tortoise and Hare)

Two pointers start together and move in the same direction, one step and two steps at a time. Two facts drive every problem in this family:

• When fast reaches the end, slow is at the middle.
• If there's a cycle, fast gains one step per iteration on slow inside it, so they must meet within one lap of the cycle.

Linked List Cycle II: finding where the cycle starts (LeetCode 142)

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                 # inside the cycle
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p                     # cycle start
    return None

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
}

The proof, which interviewers do ask for. Let a be the distance from head to the cycle start, b the distance from the cycle start to the meeting point, and c the cycle length. When they meet, slow has walked a + b and fast has walked 2(a + b). Fast's extra distance is a whole number of laps: 2(a + b) − (a + b) = mc, so a + b = mc and a = mc − b = (m − 1)c + (c − b). Now c − b is exactly the distance from the meeting point forward to the cycle start. So a pointer starting at head and a pointer starting at the meeting point, both moving one step at a time, arrive at the cycle start together.

Middle of the Linked List (876)

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow      # second middle for even length

If you need the first middle for even lengths (common when splitting a list for merge sort or for palindrome checks), loop while fast.next and fast.next.next. Getting this wrong is the standard bug in Palindrome Linked List (234) and Sort List (148); both are in the linked list problems guide.

Find the Duplicate Number (287): Floyd on an array

An array of n + 1 integers in [1, n] has at least one repeat. Treat each index i as a node with an edge to nums[i]. Since index 0 has no incoming edge and every value points to a valid index, following edges from 0 must eventually loop, and the entry of the loop is a value with two incoming edges: the duplicate.

def findDuplicate(nums):
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

It meets the problem's constraints of O(1) extra space without modifying the array, which rules out sorting and hash sets. If you can't recall it, the honest fallback is binary search on the value range (count elements ≤ mid), which is O(n log n) and also constant space. Happy Number (202) uses the same cycle-detection idea on the sequence of digit-square sums.

3Sum, 4Sum and the General k-Sum Pattern

3Sum (LeetCode 15)

Find all unique triplets summing to zero. Sort, fix the first element as an anchor, and run Two Sum II on the rest. The work is in handling duplicates without a set.

def threeSum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:
            break                         # smallest is positive: no more zeros
        if i > 0 and nums[i] == nums[i - 1]:
            continue                      # same anchor, same triplets
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1               # skip duplicate second elements
    return res

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            int s = nums[i] + nums[lo] + nums[hi];
            if (s < 0) lo++;
            else if (s > 0) hi--;
            else {
                res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                lo++;
                hi--;
                while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
            }
        }
    }
    return res;
}

Dry run on [−1, 0, 1, 2, −1, −4], sorted to [−4, −1, −1, 0, 1, 2]. Anchor −4: the best you can reach is −4 + 1 + 2 = −1, no hit. Anchor −1 (index 1): finds [−1, −1, 2] and then [−1, 0, 1]. Anchor −1 at index 2 is skipped as a duplicate. Anchor 0: lo=4, hi=5 gives 3, no hit. Result: two triplets.

Only the left pointer needs the duplicate skip. Once lo moves past duplicates, any triplet with the same lo value would need the same hi value, which the while loop will step over because the sum no longer matches. Skipping on both sides is harmless though, and some interviewers prefer seeing it.

4Sum (LeetCode 18) and a reusable k-Sum

Rather than nesting another loop by hand, write k-Sum recursively: for k > 2, fix one element and recurse with k − 1; at k = 2, run the two-pointer scan. Complexity is O(n^k−1), so 4Sum is O(n³).

def fourSum(nums, target):
    nums.sort()

    def two_sum(start, target):
        res = []
        lo, hi = start, len(nums) - 1
        while lo < hi:
            s = nums[lo] + nums[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                res.append([nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
        return res

    def k_sum(start, k, target):
        if start == len(nums):
            return []
        # pruning: k smallest remaining too big, or k largest too small
        if nums[start] * k > target or nums[-1] * k < target:
            return []
        if k == 2:
            return two_sum(start, target)
        res = []
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            for rest in k_sum(i + 1, k - 1, target - nums[i]):
                res.append([nums[i]] + rest)
        return res

    return k_sum(0, 4, target)

Related variants: 3Sum Closest (16) tracks the sum with minimum abs(s − target) instead of matching exactly. 3Sum Smaller counts pairs: when nums[i] + nums[lo] + nums[hi] < target, all hi − lo pairs with that lo qualify, so add them and move lo.

Partitioning: Dutch National Flag and Quicksort

Sort Colors (LeetCode 75)

Sort an array of 0s, 1s and 2s in one pass and O(1) space. Keep three regions: [0, low) holds 0s, [low, mid) holds 1s, (high, n−1] holds 2s, and [mid, high] is unprocessed.

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1            # do NOT move mid: swapped-in value is unseen

public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0) swap(nums, low++, mid++);
        else if (nums[mid] == 1) mid++;
        else swap(nums, mid, high--);
    }
}

private void swap(int[] a, int i, int j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

Why can mid advance after swapping with low but not with high? The element that comes from low is from the already-processed 1s region (or is the same element when low == mid), so it's known to be a 1. The element that comes from high hasn't been looked at yet. Dry run on [2, 0, 2, 1, 1, 0]:

The same three-way partition is what makes quicksort robust to many duplicate keys, and the two-way version (Lomuto or Hoare) is the core of quicksort and quickselect. Both are covered with code in sorting algorithms compared and applied in Kth Largest Element.

Pointers on Two Sequences: Merge and Subsequence

Merge Sorted Array (LeetCode 88)

nums1 has room for both arrays at the end. Merging from the front would overwrite unread nums1 elements; merging from the back fills slots that are guaranteed empty.

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else nums1[k--] = nums2[j--];
    }
}

Looping on j >= 0 rather than both indices is deliberate: once nums2 is exhausted, the remaining nums1 elements are already in place.

Is Subsequence (LeetCode 392)

def isSubsequence(s, t):
    i = 0
    for c in t:
        if i < len(s) and s[i] == c:
            i += 1
    return i == len(s)

Greedy matching is optimal: matching s[i] to the earliest possible occurrence in t never hurts. The follow-up ("billions of s strings against one t") flips the approach to precomputing, for each character, a sorted list of positions in t and binary searching the next position.

How to Choose the Right Two Pointer Pattern

The last row trips people up. Sorting to enable two pointers costs O(n log n) and destroys the original indices. If the problem wants indices from an unsorted array, a hash map is simpler and faster.

Two Pointers in Interviews: What Gets Probed

Two pointer solutions are short, so interviewers fill the time with questions about why they work. Plan for these:

• "Why is it safe to move that pointer?" Have the elimination argument ready for every opposite-ends problem you solve. "We discard row lo because every remaining partner gives a smaller sum" is a complete answer.
• "What's the complexity including the sort?" O(n log n) for two-sum-style problems on unsorted input, dominated by sorting. For 3Sum, the O(n²) scan dominates the sort.
• "Can you do it without modifying the input?" For Find Duplicate, that rules out sorting and marking; Floyd is the answer.
• "How do you handle duplicates?" Explain the skip logic instead of reaching for a set.
• "Prove the cycle-start trick." Write a, b, c on the whiteboard and derive a = (m−1)c + (c − b).

A practice order that builds the intuition

1. Warm-up: 125 Valid Palindrome, 167 Two Sum II, 977 Squares of Sorted Array, 344 Reverse String.
2. Read/write: 26, 80, 27 Remove Element, 283 Move Zeroes.
3. Fast/slow: 141, 142, 876, 19 Remove Nth Node From End, 287, 202.
4. k-Sum: 15 3Sum, 16 3Sum Closest, 18 4Sum, 611 Valid Triangle Number.
5. Greedy elimination: 11 Container With Most Water, 42 Trapping Rain Water, 881 Boats to Save People.
6. Partitioning: 75 Sort Colors, 905 Sort Array by Parity, 215 Kth Largest via quickselect.

About 25 problems, and you'll have seen every family more than once. Then mix them into timed sets alongside other patterns from the top DSA patterns list, so the hard part, recognising which family you're in, gets practice too.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.