Two Pointers (Boards)

Move nonzero values in [0,1,0,3] to the front. One pointer reads the next input; another writes the next result. Mark processed and unprocessed regions before moving either pointer.

Every version obeys two principles:

1. The physical meaning of every region must hold at the end of every step. For example, "[0, slow) holds the kept elements, in their original order." As long as that sentence stays true, the answer is sitting there when the loop ends.
2. Each step shrinks the unknown region by at least one, and the loop stops when the unknown region is empty. Otherwise you loop forever or skip the last element. The while condition is a literal translation of "the unknown region is not empty."

Each step below adds exactly one idea to the previous one:

When to Use This Pattern

The brute-force way to remove in place is: when you see an element to delete, shift everything after it left by one. That is O(n) per deletion and O(n²) in the worst case. Worse, deleting while walking forward easily skips elements. Take nums = [1, 2, 2, 3] and remove every 2 with pop(i) while doing i += 1:

The board method never shifts a block. fast looks at each element once from left to right, and anything worth keeping is copied to slow's position. Each element is read at most once and written at most once: O(n) time, O(1) extra space, and nothing is skipped.

Opposite-direction pointers are fast for a different reason. Two nested loops try every (i, j) pair; on a sorted array, each comparison shows that one end "cannot pair with anyone", so a whole row of pairs is discarded at once and O(n²) becomes O(n).

The longest or shortest contiguous subarray or substring also uses two indices moving the same way, but there [l, r] is the window you want rather than a discarded region; that lives in the Sliding Window article.

Recognition Checklist

• The problem asks you to modify the array in place and return the new length
• The array is sorted (or sorting doesn't change the answer) and you need a pair or tuple meeting a condition
• You compare or swap from both ends toward the middle (palindromes, reversal)
• The array has only a few distinct values and like values must be grouped together
• Two sorted sequences need to be merged or aligned element by element

Before You Code

Answer these three before writing code.

1. How many boards, and what does each region mean? Write each region as an interval and mark which ends are open. For example, [0, slow) is the result to keep, [slow, fast) was seen and discarded, [fast, n) has not been seen.
2. What do you look at each step, how many cases are there, and how do the boards move in each case? After the move, every sentence from the first question must still be true.
3. When do you stop, and what do you return? Stop when the unknown region is empty: if it is [fast, n) the condition is fast < n; if it is the closed interval [i, j] the condition is i <= j. The return value is usually the length of the result region, not the last index written.

The three answers chain together: the first fixes the regions, the second keeps them true, and the third reads the loop condition straight off how the unknown region is written.

Try it on LC 27 Remove Element, deleting every element equal to val:

• Two boards, slow and fast. [0, slow): seen and kept, original order; [slow, fast): seen and equal to val; [fast, n): not seen yet.
• Each step looks at nums[fast]. Not equal to val: copy it to nums[slow], and both slow and fast move forward; equal to val: only fast moves. In both cases all three regions keep their meaning.
• When fast reaches n the unknown region is empty; return slow.

Step 1 turns this paragraph into code.

Move Zeroes (LeetCode 283)

Given an integer array, move all zeros to the end in place while preserving nonzero order and the total number of elements; return nothing. The expected output below describes the mutated array, not a newly returned array.

Input: nums = [0, 1, 0, 3, 12]. Expected: [1, 3, 12, 0, 0].

Regions at every step: [0, slow) = non-zero values we keep, in original order; [slow, fast) = zeros; [fast, n) = not looked at yet.

1. Walk it by hand

2. Read the rule off the table

• fast moves one step on every row.
• If nums[fast] is not zero, swap it into nums[slow] and add 1 to slow.
• If it is zero, do nothing; it stays in the zero region between slow and fast.

3. Turn each row into code

def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Core Templates

All five steps use the same routine: answer the three questions, then check every case against the two principles. Do the regions still mean what they should after the move? Did the unknown region shrink?

Step 1: Same-direction boards: two boards, three regions

Problem: remove every element equal to val in place and return how many remain (LC 27).

The input is an integer array nums and a value val. Return k, the number of elements not equal to val. In addition, the first k entries of nums must be exactly those elements. Whatever comes after index k − 1 is not checked, and the problem does not require keeping the original order (the code below happens to keep it). The array cannot actually shrink; you can only overwrite its front.

For example, [3, 2, 2, 3] with val = 3 → return 2, and the first 2 entries are [2, 2]. Both the return value and the prefix must be right.

The three questions are answered above. fast goes ahead to look at new elements; slow moves forward only when something is kept, fencing the result in on its left.

def remove_element(nums, val):
    slow = 0                        # [0, slow) kept; [slow, fast) discarded; [fast, n) unseen
    for fast in range(len(nums)):   # fast takes 0, 1, ..., n-1 in turn
        if nums[fast] != val:       # keep it: put it at the end of the kept region
            nums[slow] = nums[fast]
            slow += 1
    return slow                     # length of the kept region


a = [3, 2, 2, 3]
assert remove_element(a, 3) == 2 and a[:2] == [2, 2]   # a[:2] is a slice: a new list of indices 0 and 1
b = [0, 1, 2, 2, 3, 0, 4, 2]
assert remove_element(b, 2) == 5 and b[:5] == [0, 1, 3, 0, 4]
assert remove_element([], 1) == 0
assert remove_element([1, 1], 1) == 0

nums = [3, 2, 2, 3], val = 3:

At the end [0, 2) is [2, 2]. Whatever sits at indices 2 and 3 doesn't matter; they belong to the discarded region.

One more step: move zeros to the end, keeping the order of non-zeros (LC 283)

The input is an integer array nums. Modify it in place and return nothing new. Move every 0 to the end; the non-zero values keep their relative order, and the number of zeros stays the same.

For example, [0, 1, 0, 3] → [1, 3, 0, 0].

How this differs from LC 27: LC 27 only checks the first k entries, but here the whole array is the output, and the back must be exactly those zeros.

Think first: If you just call remove_element(nums, 0), the front comes out right. What is left at the back? To keep [slow, fast) all zeros at every step, what should you do with a kept element instead?

def move_zeroes(nums):
    slow = 0                        # [0, slow) non-zero, original order; [slow, fast) all zeros
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]   # swap, don't overwrite
            slow += 1
    return nums


assert move_zeroes([0, 1, 0, 3]) == [1, 3, 0, 0]   # the example from the statement
assert move_zeroes([0, 1, 0, 3, 12]) == [1, 3, 12, 0, 0]
assert move_zeroes([0, 0]) == [0, 0]
assert move_zeroes([1]) == [1]
assert move_zeroes([]) == []

One more step: remove extra spaces

Practice here (original problem) ↗

The input is a string. Return a new string with all leading and trailing spaces removed and every run of spaces in the middle collapsed to one.

For example, " abc de " → "abc de".

Think first: slow and fast still move the same way. Can you decide whether to keep a space by looking at the space alone? Which character do you need to look at to know "a space has already been kept"? When you see a trailing space inside the loop, can you tell it is trailing?

def remove_spaces(s):
    a = list(s)                     # Python strings are immutable; a list of characters can be edited in place
    slow = 0
    for fast in range(len(a)):
        if a[fast] == " " and (slow == 0 or a[slow - 1] == " "):
            continue                # a leading space, or a space right after a space: drop it
        a[slow] = a[fast]
        slow += 1
    if slow > 0 and a[slow - 1] == " ":
        slow -= 1                   # there may be one trailing space left
    return "".join(a[:slow])        # glue the first slow characters back into a string


assert remove_spaces("  abc  de  ") == "abc de"
assert remove_spaces("a") == "a"
assert remove_spaces("   ") == ""
assert remove_spaces("") == ""

Variant: the result region on the right, writing from the back (LC 88 Merge Sorted Array)

The inputs are nums1, m, nums2, n. nums1 has length m + n: its first m entries are valid data and its last n entries are placeholders whose values don't matter. nums2 holds n valid entries. Both valid parts are nondecreasing.

Merge them into one nondecreasing sequence written into nums1 in place, returning nothing new (the code below returns nums1 only so the asserts are easy to write).

For example, nums1 = [1, 3, 0, 0], m = 2 and nums2 = [2, 4], n = 2 → nums1 becomes [1, 2, 3, 4]. A valid value may itself be 0, so you can't tell placeholders apart by checking for 0.

Think first: If you write from the front, what happens on the first write to index 0? Which part of nums1 is empty and safe to write into? If you start writing there, which number goes in at each step?

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1   # (p, m+n) is the sorted result region
    while p2 >= 0:                  # done once nums2 is used up; nums1's rest is already in place
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    return nums1


assert merge([1, 3, 0, 0], 2, [2, 4], 2) == [1, 2, 3, 4]   # the example from the statement
assert merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3) == [1, 2, 2, 3, 5, 6]
assert merge([4, 5, 0], 2, [1], 1) == [1, 4, 5]
assert merge([0], 0, [1], 1) == [1]
assert merge([1], 1, [], 0) == [1]

Variant: one read pointer per sequence (LC 986 Interval List Intersections)

The input is two interval lists A and B (firstList and secondList on LeetCode). Each list is sorted by start, and its intervals don't overlap one another. All intervals are closed: [a, b] includes both a and b. Return every intersection of an interval from A with one from B, from left to right.

For example, A = [[0, 2]] and B = [[2, 5]] → [[2, 2]]: the two intervals share only the endpoint 2, which still counts. If either list is empty, return an empty list.

Think first: How do you compute the intersection of [a1, b1] and [a2, b2], and when is it empty? After handling this pair, which interval can be dropped? Could it still meet a later interval of the other list?

def interval_intersection(A, B):
    i = j = 0                       # A[:i] and B[:j] are done
    res = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:                # closed intervals: lo == hi is an intersection too
            res.append([lo, hi])
        if A[i][1] < B[j][1]:       # the one that ends first can't intersect anything later
            i += 1
        else:
            j += 1
    return res


assert interval_intersection([[0, 2]], [[2, 5]]) == [[2, 2]]   # the example from the statement
assert interval_intersection([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]]) == [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
assert interval_intersection([[1, 3]], []) == []
assert interval_intersection([[1, 7]], [[3, 10]]) == [[3, 7]]

Step 1 recap

• What it solves: filtering, moving and merging in place in O(n) time and O(1) extra space, each element read at most once and written at most once.
• The key line: if keep: nums[slow] = nums[fast]; slow += 1, then return slow.
• What the variants change: LC 283 swaps instead of copying, so [slow, fast) stays all zeros; removing spaces decides "keep?" by looking at the last character of the result; LC 88 puts the result region on the right and writes from the back; LC 986 gives each sequence its own read pointer and advances whichever ends first.
• Easiest mistake: returning slow - 1 or the last index written. [0, slow) is the result region, so its length is slow.

In Step 1, whether to keep an element depends only on the element itself. In dedup problems it also depends on what has already been kept. That is Step 2.

Step 2: Dedup: compare with the result region

Problem: in a sorted array, keep each value at most k times and return the new length (k = 1 is LC 26, k = 2 is LC 80).

The input is a nondecreasing array nums and k. Rewrite it in place so that each value appears at most k times; the kept numbers stay in their original order at the front (so they are still sorted). Return how many were kept; whatever comes after is not checked. LeetCode fixes k = 1 for LC 26 and k = 2 for LC 80; here it is one function with a parameter k.

For example, [1, 1, 1, 2, 2, 3]: k = 1 → return 3 with prefix [1, 2, 3]; k = 2 → return 5 with prefix [1, 1, 2, 2, 3].

The three questions:

• Regions: [0, slow) is the deduplicated result, [slow, fast) is discarded, [fast, n) is unseen.
• Each step looks at nums[fast]: if the result already holds k copies of this value, drop it; otherwise keep it.
• Stop when fast reaches n; return slow.

How do you tell "the result already holds k copies"? The array is sorted, so equal values form one contiguous block at the end of the result region. Just look at the k-th from last element of the result, nums[slow - k]: if it equals nums[fast], the last k elements all equal nums[fast].

The slow < k at the front of the condition: with fewer than k elements kept, the result can't already hold k copies, so keep the element. It also guards against slow - k going negative, which would read an element from the end of the array. or short-circuits: when slow < k is true, the second half is never evaluated.

def dedup_keep_k(nums, k):
    slow = 0                        # [0, slow) is the result, each value at most k times
    for fast in range(len(nums)):
        if slow < k or nums[fast] != nums[slow - k]:   # compare with the k-th from last kept
            nums[slow] = nums[fast]
            slow += 1
    return slow


a = [1, 1, 1, 2, 2, 3]
assert dedup_keep_k(a, 2) == 5 and a[:5] == [1, 1, 2, 2, 3]
c = [1, 1, 1, 2, 2, 3]
assert dedup_keep_k(c, 1) == 3 and c[:3] == [1, 2, 3]   # the example from the statement, k = 1
b = [0, 0, 1, 1, 1, 2]
assert dedup_keep_k(b, 1) == 3 and b[:3] == [0, 1, 2]
assert dedup_keep_k([], 2) == 0
assert dedup_keep_k([7, 7, 7], 3) == 3

Why not compare with nums[fast - k]. That position belongs to the original array and may already have been overwritten. [1, 1, 1, 2, 2, 2, 3], k = 2:

The result keeps only one 2; the second 2 was wrongly dropped. Comparing with nums[slow - k], at fast = 4 slow is 3, so it checks nums[1] = 1 and keeps the 2, which is correct. The reason is the first principle: the only thing you can rely on is the meaning of the result region, and the [slow, n) part of the original array can be rewritten at any moment.

One more step: keep none of the repeated values (dedup III)

Practice here (original problem) ↗

The input is a nondecreasing array. Rewrite it in place: delete every value that appears more than once, keep only the values that appear exactly once, in their original order at the front, and return how many were kept.

For example, [1, 2, 2, 3, 3, 3, 4] → return 2 with prefix [1, 4].

Think first: Dedup II can decide on each number as soon as it sees it, because "the result already holds k copies" settles the question. Here, when you see the first 2, can you decide whether to keep it? What else do you need to know?

def dedup_drop_all(nums):
    slow = fast = 0                 # [0, slow) holds values that appear exactly once
    while fast < len(nums):
        end = fast
        while end < len(nums) and nums[end] == nums[fast]:
            end += 1                # [fast, end) is one whole block of equal values
        if end - fast == 1:         # the block has a single element: keep it
            nums[slow] = nums[fast]
            slow += 1
        fast = end                  # block done, jump to the next one
    return slow


a = [1, 2, 2, 3, 3, 3, 4]
assert dedup_drop_all(a) == 2 and a[:2] == [1, 4]
assert dedup_drop_all([5, 5]) == 0
assert dedup_drop_all([5]) == 1
assert dedup_drop_all([]) == 0

One more step: repeatedly remove adjacent duplicates (dedup IV)

Practice here (original problem) ↗

The input is a string. Whenever two or more equal characters sit next to each other, delete that whole run; after a deletion the characters on both sides may meet and form a new run, which is deleted too, until nothing more can be removed. Return what is left.

For example, "abbbaaccz" → "z": delete bbb to get "aaaccz", where the first a and the following aa now form aaa, which goes; then cc goes, leaving "z".

Think first: After deleting a run, you have to look back at "the last character kept so far" to see whether it joins what follows. With characters going on and coming off the end of the result region [0, slow) like this, which data structure is it acting as? When a run is deleted, how should slow move?

def remove_adjacent_repeatedly(s):
    a = list(s)
    slow = fast = 0                 # [0, slow) is a stack, a[slow - 1] is its top
    while fast < len(a):
        if slow > 0 and a[fast] == a[slow - 1]:
            while fast < len(a) and a[fast] == a[slow - 1]:
                fast += 1           # skip the whole run equal to the top
            slow -= 1               # and remove the top too
        else:
            a[slow] = a[fast]       # push
            slow += 1
            fast += 1
    return "".join(a[:slow])


assert remove_adjacent_repeatedly("abbbaaccz") == "z"
assert remove_adjacent_repeatedly("abba") == ""
assert remove_adjacent_repeatedly("abc") == "abc"
assert remove_adjacent_repeatedly("") == ""

Step 2 recap

• What it solves: dedup where keeping a number depends on what has already been kept.
• The key line: if slow < k or nums[fast] != nums[slow - k]: compare with the result region, not the original array.
• What the variants change: only "compare with what", as in the table below. Dedup III looks at the length of the whole block; dedup IV treats the result region as a stack, compares with the top, and on a match skips the run and pops.
• Easiest mistake: comparing with the original nums[fast - k]. That slot may already be overwritten, and [1, 1, 1, 2, 2, 2, 3] with k = 2 keeps only one 2.

In the first two steps the boards move the same way and the result keeps its original order. If order doesn't matter, the boards can start from both ends and move inward. That is Step 3.

Step 3: Partitioning: boards from both ends

Problem : quicksort's partition. Given the range [l, r] with nums[r] as the pivot, put everything smaller than the pivot on the left and eve… (Pro lesson)

One more board: three boards, four regions (LC 75 Sort Colors)

The input is an array containing only 0, 1 and 2 (three colors). Rearrange it in place so all 0s come first, then 1s, then 2s. (Pro lesson)

Step 3 recap

What it solves : splitting elements into two or three groups in place when order doesn't need to be kept. (Pro lesson)

Step 4: Opposite boards: reversal and palindromes

Problem : reverse the slice a[l..r] in place ( LC 344 reverses the whole array). (Pro lesson)

One more step: palindromes (LC 125)

The input is a string s . Looking only at letters and digits and ignoring case, decide whether it is a palindrome and return True or False; (Pro lesson)

One more step: delete at most one character (LC 680)

The input is a string of lowercase letters. Decide whether deleting at most one character (possibly none) can make it a palindrome. (Pro lesson)

Variant: three-step reversal (LC 189 Rotate Array)

The input is a non-empty integer array nums and a non-negative integer k. (Pro lesson)

One more step: reverse the order of words (LC 151)

The input is a string of words separated by spaces, possibly with extra spaces (leading, trailing, or several in a row). (Pro lesson)

Step 4 recap

What it solves : handling elements in mirror positions as pairs: reversal, palindrome checks, rotation. (Pro lesson)

Step 5: Opposite squeeze: each move discards a batch

Problem : in a sorted array, find two numbers that sum to target and return 1-based indices ( LC 167 Two Sum II). (Pro lesson)

One more step: container with the most water (LC 11)

The input is a non-negative integer array h ( height on LeetCode), where h[i] is the height of the i-th vertical line. (Pro lesson)

One more step: boats to save people (LC 881)

The input is a weight array people and a boat capacity limit ; nobody weighs more than limit. (Pro lesson)

One more step: trapping rain water (LC 42)

The input is a non-negative integer array h ( height on LeetCode): the heights of a row of bars, each 1 wide. (Pro lesson)

Variant: fix one in an outer loop, and the inside is Two Sum II (LC 15 3Sum)

The input is an integer array. Return every triplet that sums to 0. The triplets are values , not indices. (Pro lesson)

One more layer: 4Sum (LC 18)

The input is nums and target. Return every quadruplet of values summing to target. The four numbers come from four different positions; (Pro lesson)

Step 5 recap

What it solves : finding a pair (or a tuple) meeting a condition in a sorted array, turning O(n²) enumeration into an O(n) squeeze. (Pro lesson)

The five steps together

Step Boards Regions Loop condition Key move Step 1 slow, fast, same direction [0, slow) kept, [slow, fast) discarded, [fast, n) unseen fast… (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem is phrased) Underlying problem Step LC 283 move zeros to the end, keep the order same-direction boards, swap non-z… (Pro lesson)

Common Pitfalls

Returning the last written index, or slow - 1 . The problem wants the new length: removing 3 from [3, 2, 2, 3] should return 2. (Pro lesson)

Say It in the Interview

Lead with the boards and what each region means; (Pro lesson)