Two Pointers — Same Direction

Before we start

If you finished the previous chapter on opposite-end two pointers, this one will feel like a natural cousin. If this is your first time here, no worries — we start from zero. By the end you will be able to:

• See the slow-fast pointer idea as a concrete mental picture, not just code.
• Explain out loud why writing to the slow pointer never destroys important data.
• Recognise this pattern in problems that look completely different on the surface.

When you see a Pause & Think box, actually stop. Do not read ahead. That five-second effort is what makes the idea stick.

Picture this first (no code yet)

That factory image is the algorithm. The fast hand is the fast pointer; the slow hand placing keepers is the slow pointer. We'll make this precise — but never lose the factory picture.

The actual problem

Let's make it concrete. You have this sorted array and need to remove all duplicates, in-place:

input  : [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
output : [0, 1, 2, 3, 4]   (return length = 5)

In-place means you cannot create a new array. You must rearrange the original memory. The result sits in the first 5 positions; whatever comes after doesn't matter.

First, the slow way (so you feel the pain)

Approach 1 — extra memory (not allowed):

# Collect unique values into a fresh list — O(n) space
unique = []
for x in arr:
    if not unique or unique[-1] != x:
        unique.append(x)
return unique

This works but uses O(n) extra memory. The problem forbids it.

Approach 2 — shift everything (too slow):

When a duplicate is found at position i, shift every element after it one step to the left — like pulling a book out of a shelf and sliding all the others over.

# Shift approach — allowed in memory, but...
i = 1
while i < n:
    if arr[i] == arr[i - 1]:
        for j in range(i, n - 1):   # shift everything left
            arr[j] = arr[j + 1]
        n -= 1
    else:
        i += 1

Count the work. On an array where every element is a duplicate ([0,0,0,…,0]), every element triggers a full shift:

n = 10           →  ~45 shift operations
n = 1,000        →  ~500,000 shift operations
n = 100,000      →  ~5,000,000,000 shift operations  (five billion!)

We need O(1) space (no extra array) and O(n) time (no shifting). The two-pointer trick gives us exactly that.

The turning point

Back to the factory. The brilliant realisation is this: the inspector doesn't need to move the rest of the belt when she tosses a bottle. She just places the next keeper directly into the next clean slot, no matter how many cracked bottles have been skipped in between.

Here is why it is always safe: the slow pointer (clean-section end) can never get ahead of the fast pointer (inspector). The fast pointer must reach position 3 before the slow pointer can write there — and once the fast pointer has passed a position, its original value has already been "seen." It's either already saved in the clean section, or it was a duplicate we deliberately threw away. Either way, that slot is free real estate.

Slow never overtakes fast. So overwriting is always safe.

The one idea to remember

That sentence is the algorithm. Everything else is applying it with different "keeper" rules.

Watch it happen, frame by frame

Let's trace Remove Duplicates on [0, 0, 1, 1, 2]. The slow pointer marks the next write slot. fast scans every position.

Initial state:
index:  0    1    2    3    4
value: [0    0    1    1    2]
        ↑
      slow=1  (position 0 is always a keeper — first element stays)
      fast starts at 1

fast=1 → value 0
  Compare with last written: arr[slow-1] = arr[0] = 0
  0 == 0  →  DUPLICATE, skip.  slow stays at 1.

fast=2 → value 1
  Compare with last written: arr[slow-1] = arr[0] = 0
  1 ≠ 0  →  KEEPER. Write arr[slow] = 1.  slow = 2.
  Array: [0, 1, 1, 1, 2]

fast=3 → value 1
  Compare with last written: arr[slow-1] = arr[1] = 1
  1 == 1  →  DUPLICATE, skip.  slow stays at 2.

fast=4 → value 2
  Compare with last written: arr[slow-1] = arr[1] = 1
  2 ≠ 1  →  KEEPER. Write arr[slow] = 2.  slow = 3.
  Array: [0, 1, 2, 1, 2]

fast exhausted.  Return slow = 3.
Valid portion: arr[0..2] = [0, 1, 2]  ✅

slow=1, fast scans:
fast=1: 1==1  → skip
fast=2: 2≠1  → write arr[1]=2, slow=2.  Array: [1,2,2,2,2,3]
fast=3: 2==2  → skip
fast=4: 2==2  → skip
fast=5: 3≠2  → write arr[2]=3, slow=3.  Array: [1,2,3,2,2,3]
Return 3.  Valid: [1, 2, 3]  ✅

Now, the code — line by line

def remove_duplicates(nums):
    if not nums:
        return 0

    slow = 1            # position 0 is always valid; start write head at 1

    for fast in range(1, len(nums)):              # fast scans every position from 1
        if nums[fast] != nums[slow - 1]:          # is this a keeper?
            nums[slow] = nums[fast]               # write it into the clean section
            slow += 1                             # advance the write head

    return slow                                   # length of the clean section

Mapping every line back to the factory story:

• slow = 1 — The clean section already has one bottle (position 0). The write head waits at slot 1 for the next keeper.
• for fast in range(1, len(nums)): — The inspector picks up every bottle, one by one, left to right.
• if nums[fast] != nums[slow - 1]: — "Is this bottle different from the last one I placed in the clean section?" — note slow - 1, the last written slot, not fast - 1 (the previous bottle on the belt). These are different the moment any duplicate was skipped.
• nums[slow] = nums[fast] — Place the keeper into the next clean slot.
• slow += 1 — Advance the clean-section boundary.
• return slow — The clean section runs from index 0 to slow - 1; its length is slow.

Why does it never go wrong?

At every moment there is a tidy three-region picture:

[ CLEAN  |  ALREADY SEEN (reusable)  |  NOT YET INSPECTED ]
  0..slow-1   slow..fast-1               fast..n-1

1. Clean region (0 to slow-1) — holds exactly the valid, deduplicated output so far.
2. Reusable zone (slow to fast-1) — every element here has already been read by the fast pointer. If it was a keeper it's been copied to the clean region; otherwise it was a duplicate. Either way, these slots are free to overwrite.
3. Unseen zone (fast to n-1) — not yet looked at; we never touch it except via the fast pointer.

The key safety fact: slow ≤ fast at all times. Slow only advances when fast has already moved past the slot being written. So a write never clobbers an unread element.

Why is it so fast?

The fast pointer starts at index 1 and advances by 1 every iteration. It always reaches the end in exactly n - 1 steps, regardless of how many duplicates exist.

The slow pointer only advances when a keeper is found — it might advance zero times or n times. But it never adds extra work; it just decides what to do with the position the fast pointer handed it.

Total work: exactly n operations, no shifting, no nested loops.

n = 10           → 10 steps
n = 100,000      → 100,000 steps   (vs. 5,000,000,000 for shifting)

When should I reach for this? (the trigger list)

You won't be told "use slow-fast pointers." You need to smell it. Reach for this pattern when you notice:

• You're asked to filter, remove, or partition an array in-place (no extra array allowed).
• The result should preserve relative order of the surviving elements.
• The problem says things like "remove all occurrences of X," "move zeroes to end," "keep at most K duplicates."
• The brute-force idea involves shifting elements, which is O(n²).
• You can phrase the decision as: "does this element belong in the clean section?" — a yes/no question per element.

See two or more of those? Think slow (write head) + fast (scanner).

The same trick in five disguises

Each problem below looks different on the surface. But the skeleton is identical every time: fast scans, slow writes keepers, clean region grows from the left. Notice the bones.

Disguise 1 — Remove Element (LC #27)

Remove all occurrences of a given value. The keeper rule changes to "is not the target value" — that's the only difference.

def removeElement(nums, val):
    slow = 0              # even the first element might be the target, so start at 0

    for fast in range(len(nums)):
        if nums[fast] != val:          # keeper = "not the value we're removing"
            nums[slow] = nums[fast]
            slow += 1

    return slow

Same skeleton. Different keeper rule.

Disguise 2 — Move Zeroes (LC #283)

Move all zeros to the end while keeping non-zero elements in order. Keeper = "non-zero."

def moveZeroes(nums):
    slow = 0

    for fast in range(len(nums)):
        if nums[fast] != 0:            # keeper = "non-zero"
            nums[slow], nums[fast] = nums[fast], nums[slow]   # swap instead of write
            slow += 1

    # Positions slow..n-1 are automatically all zeros now (swapped there)

We use swap here instead of plain write, so zeros don't disappear — they get exchanged to the right side. The clean region grows identically; only the tool (swap vs. assign) changes.

Trace on [0, 1, 0, 3]:

fast=0: 0 == 0  → skip.           slow=0
fast=1: 1 ≠ 0  → swap(0,1) → [1, 0, 0, 3].  slow=1
fast=2: 0 == 0  → skip.           slow=1
fast=3: 3 ≠ 0  → swap(1,3) → [1, 3, 0, 0].  slow=2
Result: [1, 3, 0, 0]  ✅

Disguise 3 — Remove Duplicates II: allow at most 2 copies (LC #80)

[1,1,1,2,2,3] → [1,1,2,2,3]. Keeper rule: "we haven't already placed 2 copies of this value." Compare with the element 2 positions behind the write head instead of 1.

def removeDuplicates2(nums):
    slow = 2              # first 2 elements always stay

    for fast in range(2, len(nums)):
        if nums[fast] != nums[slow - 2]:   # is there already a pair at slow-2 and slow-1?
            nums[slow] = nums[fast]
            slow += 1

    return slow

Why slow - 2? If nums[fast] == nums[slow - 2], both positions slow-2 and slow-1 already hold this value — we've hit our limit of 2. Skip it. Otherwise it's a keeper.

This generalises perfectly: for "at most K copies," compare with nums[slow - K] and start slow = K.

Disguise 4 — Sort Array By Parity (LC #905)

Move even numbers before odd numbers. Keeper (for the front) = "is even."

def sortArrayByParity(nums):
    slow = 0

    for fast in range(len(nums)):
        if nums[fast] % 2 == 0:           # keeper = "is even"
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

    return nums

Same factory, same bones — only the keeper definition changed.

Disguise 5 — String Compression (LC #443)

Write a compressed version of a character array in-place. The slow pointer is now the write head for the compressed output, and the fast pointer groups consecutive identical characters.

def compress(chars):
    slow = 0     # write head for the compressed result
    fast = 0     # scanner

    while fast < len(chars):
        char = chars[fast]
        count = 0

        while fast < len(chars) and chars[fast] == char:
            fast += 1
            count += 1

        chars[slow] = char
        slow += 1

        if count > 1:
            for digit in str(count):
                chars[slow] = digit
                slow += 1

    return slow

The slow-fast skeleton is still there — fast groups elements, slow writes the compressed output. Slightly more logic inside the loop, but the same two-hand factory metaphor.

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll use two pointers moving in the same direction — a fast scanner and a slow write head. Everything before the slow pointer is the clean, valid output. When the fast pointer finds a keeper it writes it at slow and advances slow. Fast visits every element exactly once, so it's O(n) time and O(1) space, one pass."

For Remove Duplicates II, add:

"Since we allow up to K copies, I compare the candidate with the element K positions behind the write head. If they're equal, we already have K copies — skip it."

Check yourself

Try to answer these from memory. If you can't, re-read the relevant section — then try again.

Practice problems

Solve these in order. The first three nail the core skeleton; the last two are the boss fights.

When you can solve Remove Duplicates without looking at notes and explain the slow - 1 vs fast - 1 distinction out loud, you have fully learned this pattern.

Next up: Dutch National Flag — Three-Way Partition, where we extend this idea to three regions and sort an array of 0s, 1s, and 2s in a single pass without any comparison sort.