Advanced Two-Pointer Patterns

The three canonical flavors carry most interview problems. The five techniques on this page show up in harder ones — multi-array problems, K-sum generalizations, and the “now do it without the hash map” follow-ups.

1. K-Sum reduction — `kSum` via two-pointer

Given an array nums and a target t, return all unique tuples of k numbers from nums that sum to t.

For k = 2: opposite-ends two-pointer on the sorted array. O(n). For k = 3: fix one index, then two-pointer on the rest. O(n²). For k = 4: fix two indices, then two-pointer on the rest. O(n³). For general k: recursive reduction — fix one, recurse with k − 1 on the suffix.

def k_sum(nums, target, k):
    nums.sort()
    def helper(start, target, k):
        if k == 2:
            return two_sum_pairs(nums, start, target)
        res = []
        for i in range(start, len(nums) - k + 1):
            if i > start and nums[i] == nums[i - 1]: continue
            for sub in helper(i + 1, target - nums[i], k - 1):
                res.append([nums[i]] + sub)
        return res
    return helper(0, target, k)
 
def two_sum_pairs(nums, start, target):
    res = []
    l, r = start, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            res.append([nums[l], nums[r]])
            l += 1; r -= 1
            while l < r and nums[l] == nums[l - 1]: l += 1
            while l < r and nums[r] == nums[r + 1]: r -= 1
        elif s < target: l += 1
        else:            r -= 1
    return res

O(n^(k-1)) time. The deduplication trick — sort plus skip equal neighbors — works at every level.

2. The merge step from merge sort

Given two sorted arrays a and b, return their merged sorted result.

The classic “merge two sorted lists” trick is exactly two-pointer on two different arrays:

def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

O(n + m) time. The pointers advance independently — whichever points to the smaller value goes first.

Variants of this same shape:

Merge Two Sorted Lists (linked-list version): same logic, linked-list nodes.
Intersection of Two Arrays II (multiset intersection of two sorted arrays).
Find the Median of Two Sorted Arrays (a binary-search variant, but the conceptual baseline is two-pointer).

3. Pointers on two different arrays

When the pointers live in different arrays, the “convergence” logic is replaced by “advance the lagging one”:

Worked example: Merge Sorted Array (in place, into `a`)

nums1 has length m + n with the first m elements being its content and the rest zero-padded. nums2 has n elements. Merge nums2 into nums1 in sorted order, in place.

The clever trick: fill from the right, not the left. Walking from the right means we never overwrite an unread value.

O(m + n) time, O(1) space. Walking right-to-left is the key insight — it avoids the overwriting problem that left-to-right would cause.

4. Sliding window as a special case

The sliding-window pattern (Day 24) is actually a same-direction two-pointer where:

The “read” pointer is r, advancing every iteration.
The “write-like” pointer is l, advancing only when the window is invalid.
Both advance forward, with l <= r always.

That’s why sliding window is O(n): it’s a same-direction two-pointer whose movements are tied to a validity predicate instead of a write decision. The same amortization argument applies — each index enters and leaves the window at most once.

If you ever feel “is this sliding window or two pointers?” — they’re the same family. Sliding window is the version where you care about the window contents; two pointers is the version where you care about the pointer positions directly.

5. Squares of a Sorted Array — merge from the outside in

Given an integer array nums sorted in non-decreasing order (may contain negatives), return an array of the squares, sorted in non-decreasing order.

The brute force: square everything, then sort. O(n log n).

The clever two-pointer: the largest square is at one of the ends of the input (since the input is sorted; the most negative or most positive squares dominate). So opposite-ends pointers, comparing absolute values, filling the output from the back:

O(n) time, O(n) extra for the output (unavoidable). A factor-of-log n speedup over the obvious sort, and a beautiful application of the “fill from the back” trick.

Choosing the right tool

Symptom	Reach for
”Pair sum on sorted array” / “palindrome” / “container”	Opposite-ends two-pointer
”Remove” / “filter” / “dedup” / “partition” in place	Same-direction read/write
”Cycle in linked list” / “duplicate in array via cycle”	Fast and slow (Floyd’s)
“Find middle of linked list in one pass”	Fast and slow
”K-sum”	K-Sum reduction (recursive two-pointer)
“Merge two sorted arrays / lists”	Two-pointer on two arrays
”Merge in place into nums1 with extra space at the end”	Right-to-left two-pointer
”Sorted squares” / monotone-after-transformation	Opposite-ends, fill from the back
Subarray with a property (sum, distinct, etc.) — variable	Sliding window (same-direction variant)

Quick check

For Merge Sorted Array (in-place), why do we fill from the RIGHT (back of nums1) instead of the left?

In Squares of a Sorted Array, why is the maximum square at one of the ends of the input?

K-sum reduction takes O(n^(k-1)) time. Why isn't it O(n^k)?

Next: basic warm-up questions — valid palindrome, reverse string, two sum II, move zeroes.

Fast and Slow Pointers Basic Questions