Advanced Two-Pointer Patterns

nums1 already holds m sorted values with n empty slots at the tail; nums2 holds n more. Merge them into nums1 in place. Merge left-to-right and your first write clobbers nums1[0] before you’ve read it. The fix is almost insultingly simple: fill from the back, largest first, writing into the empty tail that’s guaranteed safe. That one reversal — plus K-sum reduction and the merge step — is what separates the textbook flavors from the problems that actually stump people.

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.

void merge(vector<int>& nums1, int m, vector<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--];
    }
}

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]; i -= 1
        else:
            nums1[k] = nums2[j]; j -= 1
        k -= 1

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--];
    }
}

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.

Recall the comparison that picks which source feeds the next (rightmost) slot — larger value wins the back:

def merge(nums1, m, nums2, n):
  i, j, k = m - 1, n - 1, m + n - 1
  while j >= 0:
      if i >= 0 and nums1[i] > nums2[j]:
          # ??? pick the larger tail value into the back slot
      # ??? pick the larger tail value into the back slot
          nums1[k] = nums2[j]; j -= 1   # otherwise nums2's value goes to the back
      k -= 1

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:

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size(), l = 0, r = n - 1, k = n - 1;
    vector<int> out(n);
    while (l <= r) {
        if (abs(nums[l]) > abs(nums[r])) {
            out[k--] = nums[l] * nums[l];
            l++;
        } else {
            out[k--] = nums[r] * nums[r];
            r--;
        }
    }
    return out;
}

def sorted_squares(nums):
    n = len(nums)
    out = [0] * n
    l, r, k = 0, n - 1, n - 1
    while l <= r:
        if abs(nums[l]) > abs(nums[r]):
            out[k] = nums[l] * nums[l]
            l += 1
        else:
            out[k] = nums[r] * nums[r]
            r -= 1
        k -= 1
    return out

public int[] sortedSquares(int[] nums) {
    int n = nums.length, l = 0, r = n - 1, k = n - 1;
    int[] out = new int[n];
    while (l <= r) {
        if (Math.abs(nums[l]) > Math.abs(nums[r])) {
            out[k--] = nums[l] * nums[l];
            l++;
        } else {
            out[k--] = nums[r] * nums[r];
            r--;
        }
    }
    return out;
}

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

Quick check

That completes the two-pointer toolkit — converging, read/write, fast/slow, and the advanced multi-array and K-sum variants — and with it the core technique chapters. The convergence and amortization arguments here are the same ones that powered sliding window: each index is touched a constant number of times, so a quadratic brute force collapses to linear. Next: basic warm-up questions (valid palindrome, reverse string, two sum II, move zeroes), then the practice set — and from here the remaining days shift from learning patterns to applying them under interview conditions.