Remove Duplicates In Place: The Reader Writer Pointer Trick

"Remove Duplicates from Sorted Array" shows up again and again in Microsoft, Amazon, Google phone screens. It is a Easy problem on paper, but the real test is whether you recognize the Two Pointers pattern quickly and code it cleanly. Part 3 of 12 in the Two Pointers arc.

The Problem

Given an integer array nums sorted in non-decreasing order, remove duplicates in place so each unique element appears once, keeping relative order. Return k, the count of unique elements; the first k slots of nums must hold them. No second array allowed — O(1) extra memory is the contract.

Input:  nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: k = 5, nums begins with [0, 1, 2, 3, 4]
Whatever sits past index k is irrelevant.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

This is the reader-writer flavor of two pointers: both indices move the same direction at different speeds. In-place compaction with order preserved, on sorted input, is a pattern signature — duplicates are always adjacent, so one comparison decides.

The Approach

Let write mark the end of the deduplicated prefix and read scan every element. Whenever nums[read] differs from nums[write], it is a new value: advance write and copy. Equal values are duplicates and the reader just walks past them.

The invariant to state: nums[0..write] is always the deduplicated version of everything read so far. Invariant-first explanations are what senior loops grade on.

Python Solution

def remove_duplicates(nums: list[int]) -> int:
    """Compact unique values to the front; return their count."""
    if not nums:
        return 0
    write = 0
    for read in range(1, len(nums)):
        if nums[read] != nums[write]:
            write += 1
            nums[write] = nums[read]
    return write + 1

Complexity

• Time: O(n) — single pass by the reader
• Space: O(1) — compaction happens inside the input array

Interview Tips and Follow-Ups

• Immediate variant: allow each value at most twice (LeetCode 80). Same skeleton — compare against nums[write - 1] instead.
• Clarify the contract early: returning a new list fails the problem even if the output looks right.
• list(dict.fromkeys(nums)) dedupes with order in Python — name it, then explain why the space contract forbids it.

If this clicked, continue the Two Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.