Same-Direction Two Pointers: Changing an Array in Place

EditorialUpdated Oct 25, 2026

Removing items without a second array

Here's the job: take [3, 2, 2, 3, 4, 3] and remove every 3, in place. No second array, and the numbers you keep must end up at the front. You return how many you kept.

The first idea most people have is to delete each 3 and shift everything after it one seat left. It works, but each delete moves the whole rest of the array. On an array of 100,000 numbers that are all 3s, that's 4,999,950,000 moves.

Two pointers do it in one pass. They both move left to right, but at different speeds: one reads every number, the other marks the seat where the next number you keep goes. That's the same-direction kind of two pointers. The last two lessons had the pointers start at opposite ends; here they start together.

In this lesson: the read/write template and why it never loses a value; removing duplicates by comparing with what you wrote; Move Zeroes; Sort Colors, which keeps three groups at once; and the mistakes that fail on real inputs.

Before this: Introduction to Two Pointers. Next: two pointers on two arrays or strings.

Removing every 3 from [3, 2, 2, 3, 4, 3] in place. The read pointer visits all six numbers; the write pointer only moves when a number is kept. Arrows show the three kept numbers moving to the front: the 2 at position 1 to seat 0, the 2 at position 2 to seat 1, and the 4 at position 4 to seat 2. The 3s are skipped. Afterwards the array is [2, 2, 4, 3, 4, 3]: the first 3 seats are the answer and the last 3 are leftovers nobody reads.

One pointer reads, one pointer writes

Keep two indexes, both starting at 0:

read walks through every number, one step at a time.
write is the next free seat at the front.

When the number at read should be kept, copy it to write and move write one seat on. When it shouldn't, do nothing: read moves on and the number is simply not copied.

Here's every step on [3, 2, 2, 3, 4, 3], removing 3:

read	Value	What happens	write after
0	3	skip it	0
1	2	keep: write it to seat 0	1
2	2	keep: write it to seat 1	2
3	3	skip it	2
4	4	keep: write it to seat 2	3
5	3	skip it	3

write ends at 3, so the first 3 seats, [2, 2, 4], are the answer. The seats after that still hold old values; the problem says to ignore them, and so does the judge.

int removeElement(vector<int>& nums, int val) {
    int write = 0;
    for (int read = 0; read < (int)nums.size(); read++) {
        if (nums[read] != val) {      // keep it: copy it to the next free seat
            nums[write] = nums[read];
            write++;
        }
    }
    return write;                     // nums[0 .. write) is the answer
}

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:         # keep it: copy it to the next free seat
            nums[write] = nums[read]
            write += 1
    return write                      # nums[:write] is the answer

static int removeElement(int[] nums, int val) {
    int write = 0;
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != val) {      // keep it: copy it to the next free seat
            nums[write] = nums[read];
            write++;
        }
    }
    return write;                     // nums[0 .. write) is the answer
}

function removeElement(nums, val) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== val) {     // keep it: copy it to the next free seat
            nums[write] = nums[read];
            write++;
        }
    }
    return write;                     // nums[0 .. write) is the answer
}

Cost: one pass, so O(n) time, and O(1) extra space: two integers, whatever the size of the array.

Why the writer never overwrites what you still need

Writing into the same array you're reading looks risky. What if write lands on a number read hasn't looked at yet?

It can't. Each step moves read by one and write by at most one, so write is never ahead of read. The only seats the writer ever touches are ones the reader has already passed, and those values have already been copied or skipped. Nothing unread is ever lost.

Put another way: everything before write is the answer so far. That one sentence tells you what to return (write), where the next kept value goes (write), and, in the next section, what to compare against (the values just before write).

Removing duplicates: compare with what you wrote

Remove Duplicates from Sorted Array keeps one copy of each value. The array is sorted, so copies sit next to each other. The question for each number becomes: is it the same as the last number I kept? The last kept number is at write - 1.

Here it is on [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

Removing duplicates with a read and a write pointer — Seats already kept are purple. The read pointer glows; a skipped number leaves the array as it is.

Remove Duplicates from Sorted Array II allows two copies of each value. Same template: compare with what you wrote two seats back, nums[write - 2]. If it's the same value, you've already kept two of them. That works for any limit k, so one function solves both problems:

keep_at_most(nums, 1) is Remove Duplicates from Sorted Array.
keep_at_most(nums, 2) is Remove Duplicates from Sorted Array II.

The first k numbers are always kept (write < k), since there's nothing to compare them with yet. Each version below runs both: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] with k = 1 keeps [0, 1, 2, 3, 4], and [0, 0, 1, 1, 1, 1, 2, 3, 3] with k = 2 keeps [0, 0, 1, 1, 2, 3, 3].

int keepAtMost(vector<int>& nums, int k) {
    int write = 0;
    for (int read = 0; read < (int)nums.size(); read++) {
        // compare with what you WROTE, k seats back: if it's the same value, you already kept k copies
        if (write < k || nums[read] != nums[write - k]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

def keep_at_most(nums, k):
    write = 0
    for read in range(len(nums)):
        # compare with what you WROTE, k seats back: if it's the same value, you already kept k copies
        if write < k or nums[read] != nums[write - k]:
            nums[write] = nums[read]
            write += 1
    return write

static int keepAtMost(int[] nums, int k) {
    int write = 0;
    for (int read = 0; read < nums.length; read++) {
        // compare with what you WROTE, k seats back: if it's the same value, you already kept k copies
        if (write < k || nums[read] != nums[write - k]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

function keepAtMost(nums, k) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        // compare with what you WROTE, k seats back: if it's the same value, you already kept k copies
        if (write < k || nums[read] !== nums[write - k]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

Why compare with the written array and not the input? Because the writes change the input. The seat two places before read may already hold a value copied from further on. The mistakes section shows the input version failing.

Move Zeroes: keep the order, then fill

Move Zeroes asks you to push every 0 to the end while keeping the other numbers in their original order. That's the same template with the rule "keep it if it isn't 0". After one pass the non-zeros sit at the front in order; every seat from write to the end then gets a 0.

Each version prints 1 3 12 0 0 for [0, 1, 0, 3, 12].

void moveZeroes(vector<int>& nums) {
    int write = 0;
    for (int read = 0; read < (int)nums.size(); read++) {
        if (nums[read] != 0) {
            nums[write] = nums[read];
            write++;
        }
    }
    for (int i = write; i < (int)nums.size(); i++) {
        nums[i] = 0;                  // every non-zero is in front, in order: the rest are zeros
    }
}

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0                   # every non-zero is in front, in order: the rest are zeros

static void moveZeroes(int[] nums) {
    int write = 0;
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != 0) {
            nums[write] = nums[read];
            write++;
        }
    }
    for (int i = write; i < nums.length; i++) {
        nums[i] = 0;                  // every non-zero is in front, in order: the rest are zeros
    }
}

function moveZeroes(nums) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== 0) {
            nums[write] = nums[read];
            write++;
        }
    }
    for (let i = write; i < nums.length; i++) {
        nums[i] = 0;                  // every non-zero is in front, in order: the rest are zeros
    }
}

The order is kept because kept numbers are written in the order they're read. That's also why this template is the right tool whenever a problem says "keep the relative order".

A common follow-up asks for one loop instead of two. Swap instead of copying: when nums[read] isn't 0, swap it with nums[write]. Every seat from write up to read holds a 0 the reader has already passed, so each swap sends one of those 0s back to where read is. When the loop ends, the zeros are already at the end, and the non-zeros still arrived in reading order. Same output:

void moveZeroes(vector<int>& nums) {
    int write = 0;
    for (int read = 0; read < (int)nums.size(); read++) {
        if (nums[read] != 0) {
            swap(nums[write], nums[read]);  // nums[write] is a 0 already passed, or this same seat
            write++;
        }
    }
}

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            # nums[write] is a 0 already passed, or this same seat
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

static void moveZeroes(int[] nums) {
    int write = 0;
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != 0) {
            int passed = nums[write];       // a 0 already passed, or this same seat
            nums[write] = nums[read];
            nums[read] = passed;
            write++;
        }
    }
}

function moveZeroes(nums) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== 0) {
            // nums[write] is a 0 already passed, or this same seat
            [nums[write], nums[read]] = [nums[read], nums[write]];
            write++;
        }
    }
}

Sort Colors: three groups in one pass

Sort Colors gives you an array of 0s, 1s and 2s and asks you to sort it in place, without a library sort. Edsger Dijkstra posed it as the Dutch national flag problem: red, white and blue stripes.

The easy answer takes two passes: count the 0s, 1s and 2s, then write them back in order. The follow-up asks for one pass, and that's where three pointers come in.

This time the array is split into four regions, kept true at every step:

[0, low): all 0s.
[low, mid): all 1s.
[mid, high]: not looked at yet.
(high, end]: all 2s.

A square bracket includes the seat at that end; a round one stops just before it. So [0, low) is seats 0 to low - 1, and (high, end] starts at high + 1.

Each step looks at nums[mid], the first unseen number:

It's a 0. Swap it with nums[low] and move both low and mid on. The number that comes back from low is a 1 (it was in the 1s region), or it's the same seat, so mid can safely move past it.
It's a 1. It's already in the right group: move mid on.
It's a 2. Swap it with nums[high] and move high back. Don't move mid. The number that just came from high hasn't been looked at, so mid stays to look at it next.

Every step shrinks the unseen region by one, so the loop ends after at most n steps: one pass, O(1) extra space. It runs while mid <= high, because the seat at high itself is still unseen.

Here's every step on [1, 2, 0, 1, 0, 2]:

low, mid, high	Array	mid sees	Move
0, 0, 5	[1, 2, 0, 1, 0, 2]	1	already in the 1s: mid moves
0, 1, 5	[1, 2, 0, 1, 0, 2]	2	swap with seat high, then high moves back; mid stays
0, 1, 4	[1, 2, 0, 1, 0, 2]	2	swap with seat high, then high moves back; mid stays
0, 1, 3	[1, 0, 0, 1, 2, 2]	0	swap with seat low, then low and mid move
1, 2, 3	[0, 1, 0, 1, 2, 2]	0	swap with seat low, then low and mid move
2, 3, 3	[0, 0, 1, 1, 2, 2]	1	already in the 1s: mid moves

Then mid passes high and the loop stops: [0, 0, 1, 1, 2, 2].

Look at rows 2 and 3. After the first swap with high, the number that came back was another 2. Because mid stayed, it caught it on the next step. Rows 4 and 5 are real swaps with low: each time, the number that comes back to mid's seat is a 1, already in the 1s region, so mid can move on.

Sort Colors on an array of 0s, 1s and 2s, partway through: 0s on the left up to low, 1s from low up to mid, an unseen middle from mid to high, and 2s after high. Three numbered panels show the three moves. 1, mid sees a 0: swap it with low, then low and mid both move. 2, mid sees a 1: mid moves. 3, mid sees a 2: swap it with high and move high only, because the number that came from high hasn't been looked at.

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = (int)nums.size() - 1;
    while (mid <= high) {             // nums[mid .. high] hasn't been looked at yet
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high]);
            high--;                   // what came from high is unseen: mid stays to look at it
        }
    }
}

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:                # nums[mid .. high] hasn't been looked at yet
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                 # what came from high is unseen: mid stays to look at it

static void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {             // nums[mid .. high] hasn't been looked at yet
        if (nums[mid] == 0) {
            int t = nums[low]; nums[low] = nums[mid]; nums[mid] = t;
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int t = nums[high]; nums[high] = nums[mid]; nums[mid] = t;
            high--;                   // what came from high is unseen: mid stays to look at it
        }
    }
}

function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {             // nums[mid .. high] hasn't been looked at yet
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;                   // what came from high is unseen: mid stays to look at it
        }
    }
}

Try it yourself

Below is Sort Colors, but you make every move. Look at the number under mid and pick what to do. A wrong move breaks one of the four regions, and the array shows you exactly where. Try the tempting one on purpose: when mid sees a 2, swap with high and move mid too.

Sort Colors by hand: pick each move and watch the four regions

When to use it

Reach for same-direction pointers when you see:

"In place" or "O(1) extra space", and you're removing, keeping or rearranging items.
"Return the new length" and "the rest of the array doesn't matter".
"Keep the relative order" of the items you keep: write them in reading order.
A few fixed groups (like 0s, 1s and 2s) to gather together in one pass.

And watch for problems that look similar but need something else:

A run of neighbouring numbers that must meet a condition, such as the longest stretch with no repeats: both pointers move the same way, but they mark a window. That's the next section, Sliding Window.
Two separate arrays or strings to merge or compare: one pointer in each. That's the next lesson.
Many different values to sort: three groups is the limit of this trick; count or sort instead.

When two pointers doesn't work

More than three groups. The four-region trick has room for exactly three groups (or "less than, equal to, greater than" a chosen value). For many values, count them or sort.
Order inside a group. Sort Colors' swaps move items past each other. For plain numbers that doesn't matter. For records that share a key but differ otherwise, it scrambles them. When that order matters, use a stable sort, or go through the input once per group and copy that group's items, in reading order, into a new array.
Strings that can't change. In Python, Java and JavaScript a string can't be edited in place. That's why String Compression gives you an array of characters to write into.
When you need the removed items too. Overwriting loses them. Copy them out first, or use a second array.

Common mistakes

Each of these is a real submission bug, shown on the smallest input that breaks it. The outputs come from running the code.

Moving mid after a swap with high. On [1, 2, 0] it returns [1, 0, 2]. The 0 that came back from high was never looked at, so it stayed in the 1s group.

Stopping at mid < high. On [1, 0] it returns [1, 0], unchanged. The loop ends before looking at the seat high points to, which is still unseen. It must be mid <= high.

Comparing with the input instead of what you wrote. For at most two copies, checking nums[read - 2] turns [1, 1, 1, 2, 2] into [1, 1, 2] instead of [1, 1, 2, 2]. By the time read reaches the last 2, the seat two before it has been overwritten with a 2, so the second 2 looks like a third copy. Compare with nums[write - 2].

Returning one too few (or one too many). Some solutions keep last, the index of the last value kept, instead of a count. Then the answer is last + 1. Return last and [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] gives 4 [0, 1, 2, 3]: the 4 is dropped. Decide what your pointer means and return accordingly. In this lesson's template, write is the count.

Check yourself

Quiz

1 / 5

Multiple choice

In Sort Colors, mid sees a 2 and swaps it with nums[high]. What happens next?

Practice problems

From easier to harder:

Remove Element: the template exactly, keep if it isn't the value.
Remove Duplicates from Sorted Array: compare with the last value written.
Move Zeroes: keep the non-zeros in order, then fill.
Remove Duplicates from Sorted Array II: the same loop with k = 2, comparing two seats back.
String Compression: read a whole group, then write its character and its count.
Sort Colors: four regions, and mid stays after a swap with high.

Next: Two Pointers on Two Arrays or Strings, where each input gets its own pointer.