The Two-Pointer Technique

The problem

You have a sorted list of a few million sensor readings, and duplicates keep sneaking in — the same value logged twice, three times, ten times in a row. Before you ship the data downstream, you need it compacted: each value kept once, in place, no extra array, because memory is tight on this device.

It sounds trivial. Then you write the obvious version, run it on the full file, and watch it crawl. Something about "the obvious version" is quietly doing a lot more work than the task actually requires.

A first attempt

The instinct is to build a fresh list of the things you've already seen, and for each new value, scan that list to check whether it is a duplicate.

def remove_duplicates_naive(nums):
    seen = []
    for x in nums:
        if x not in seen:   # this scan is the trap
            seen.append(x)
    return seen

That x not in seen walks the whole seen list every single time. For an array of length n with mostly-unique values, you do roughly n scans of a list that grows to size n — that is O(n²) time, plus O(n) extra memory you were told you don't have. On a million rows it goes from "instant" to "make a coffee."

The insight

The array is already sorted. That changes everything. If duplicates exist, they must sit next to each other. So you never need a "seen" list at all — you only need to compare each element to the one you last kept.

Now use two pointers moving in the same direction: a read pointer that scans forward through every element, and a write pointer that marks where the next unique value belongs. write lags behind read, only advancing when read finds something new. One pass, no extra memory.

How it works

nums = [1, 1, 2, 3, 3]
        w
        r →
step:  keep 1 | dup 1 | new 2 | new 3 | dup 3
result: [1, 2, 3, _, _]   length = 3

The code

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
}

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int write = 1;
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[write - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
}

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int write = 1;
    for (int read = 1; read < numsSize; read++) {
        if (nums[read] != nums[write - 1]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int write = 1;
    for (int read = 1; read < (int)nums.size(); read++) {
        if (nums[read] != nums[write - 1]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

Complexity

The read pointer touches each element once and write never overtakes it, so the whole pass is linear with no extra allocation.

When to use it

Practice

Recap

• Two pointers moving in the same direction (a slow write, a fast read) compact or filter an array in one linear pass with no extra memory.
• The trick works because sorted order puts equal elements next to each other, so a local comparison replaces a global search.
• Whenever a naive solution scans "everything seen so far," check if a second pointer can carry that state instead — O(n²) often collapses to O(n).