What is the brute force approach and complexity for Remove Element?

Copy the kept elements into an extra array, then copy them back with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Remove Element?

read visits every element; write marks where the next kept element goes with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Remove Element?

Look for key signals in the prompt: "remove … in place" indicates No second array → we must reuse the front of `nums` as the output.; "return k, the first k elements are checked" indicates The answer is a prefix `nums[0 … k−1]` → a `write` pointer that marks the end of that prefix.; "keep elements that are not val" indicates A simple keep/skip decision per element → a `read` pointer that visits each one once..

Remove Element

Easy·LeetCode #27Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTwo Pointers (same direction: read / write)

Complexity:O(N)→O(N)

Key Insight

Do the brute force, but let the front of nums itself be the kept array. read walks over every element. write is the size of the kept part, which is also the next free slot. When nums[read] should stay, copy it to nums[write] and move write forward. When it is val, skip it.

Core Validity Invariant

The rule we keep true after every step: nums[0 … write−1] holds exactly the kept (non-val) elements we have seen so far, and nothing else. In simple words: everything before write is already the final answer.

Problem

You are given an integer array nums and a number val.

Remove every copy of val from nums in place — you may not create a second array to return. Then return k, the number of elements that are not equal to val.

After your function runs, the first k slots of nums must hold exactly those kept elements. Their order does not matter, and whatever is left after slot k − 1 is ignored.

Input

An integer array nums and an integer val.

Output

An integer k. The judge also checks that nums[0 … k−1] holds the elements that are not val (in any order).

Example 1

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

Output: 2, nums = [2, 2, _, _]

The two 3s are removed. The first 2 slots hold the two 2s. The _ slots can be anything.

Example 2

Input: nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2

Output: 5, nums = [0, 1, 3, 0, 4, _, _, _]

Five elements are not 2. They fill the first 5 slots, in any order.

Constraints

• 0 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 50
• 0 ≤ val ≤ 100

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What does the judge actually look at after my function returns — the whole array, or only part of it?
2.
If I were allowed a second array, how would I solve it? What stops me from doing that here?
3.
When I keep an element, which slot should it go into?
4.
Can writing a kept element ever destroy an element I have not looked at yet?
5.
Does the order of the kept elements matter?

Brute force approach

Idea

Walk through nums and push every element that is not val into a new array kept. Then copy kept back into the front of nums and return its size.

Thinking process

1
The easiest way to "remove" things is to build a new list that simply leaves them out.
2
So I walk nums and append every element that is not val to kept.
3
The problem wants the answer inside nums, so I copy kept back into nums[0 … k−1].
4
It works, but it uses a whole second array, which the problem asks us to avoid.

Code & Implementation

brute.cpp

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // Collect every element we want to keep in a fresh array.
        vector<int> kept;
        for (int x : nums) {
            if (x != val) kept.push_back(x);
        }

        // Copy the kept elements back to the front of nums.
        for (int i = 0; i < (int)kept.size(); i++) {
            nums[i] = kept[i];
        }
        return kept.size();
    }
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int removeElement(int[] nums, int val) {
        // Collect every element we want to keep in a fresh array.
        List<Integer> kept = new ArrayList<>();
        for (int x : nums) {
            if (x != val) {
                kept.add(x);
            }
        }

        // Copy the kept elements back to the front of nums.
        for (int i = 0; i < kept.size(); i++) {
            nums[i] = kept.get(i);
        }
        return kept.size();
    }
}

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        # Collect every element we want to keep in a fresh array.
        kept = [x for x in nums if x != val]

        # Copy the kept elements back to the front of nums.
        for i in range(len(kept)):
            nums[i] = kept[i]

        return len(kept)

export function removeElement(nums: number[], val: number): number {
    // Collect every element we want to keep in a fresh array.
    const kept: number[] = [];
    for (const x of nums) {
        if (x !== val) kept.push(x);
    }

    // Copy the kept elements back to the front of nums.
    for (let i = 0; i < kept.length; i++) {
        nums[i] = kept[i];
    }
    return kept.length;
}

Complexity

Time O(N)Space O(N)

Fast, but it breaks the "in place" rule because kept can be as big as nums. The other obvious idea — call nums.erase() each time you find val — stays in place but is O(N²), because every erase shifts all the later elements left by one.

Optimized approach

Idea

Start from brute force

The brute force builds kept in a separate array, then copies it back into the front of nums.

Find the repeated work

The extra array is not needed. The kept part grows from the left, one element at a time, and it can never grow faster than we read. So the front of nums — slots we have already read — is free space we can reuse as kept.

Define the state — what variables do I need?

read: The element we are looking at right now. It visits every index once, left to right.
write: How many elements we have kept so far. It is also the slot where the next kept element goes.
nums[0 … write−1]: The final answer so far: exactly the elements that are not `val`, among everything read up to now.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

nums[read] != val

nums[write] = nums[read]; write++

This element belongs in the answer, so it goes into the next free answer slot. It is safe because write ≤ read: the slot we overwrite holds an element we already looked at (either a val we skipped, or the same element we are copying).

nums[read] == val

do nothing (only read moves)

This element must disappear. Not copying it is how we remove it. Later kept elements will overwrite its slot if needed.

Every step

read++

Every element must be checked exactly once.

What does the current window add to the answer?

Each kept element adds one slot to the answer at the front. When read finishes, the rule says nums[0 … write−1] is exactly all the non-val elements, so write is k.

Code & Implementation

optimal.cpp

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // nums[0 .. write-1] always holds exactly the kept elements seen so far.
        int write = 0;
        for (int read = 0; read < (int)nums.size(); read++) {
            if (nums[read] != val) {
                // Keep it: put it in the next free slot of the answer.
                // write <= read, so we never overwrite an element we haven't read yet.
                nums[write] = nums[read];
                write++;
            }
            // else: skip it. write stays where it is.
        }
        return write;
    }
};

class Solution {
    public int removeElement(int[] nums, int val) {
        // nums[0 .. write-1] always holds exactly the kept elements seen so far.
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != val) {
                // Keep it: put it in the next free slot of the answer.
                // write <= read, so we never overwrite an element we haven't read yet.
                nums[write] = nums[read];
                write++;
            }
            // else: skip it. write stays where it is.
        }
        return write;
    }
}

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        # nums[0 .. write-1] always holds exactly the kept elements seen so far.
        write = 0
        for read in range(len(nums)):
            if nums[read] != val:
                # Keep it: put it in the next free slot of the answer.
                # write <= read, so we never overwrite an element we haven't read yet.
                nums[write] = nums[read]
                write += 1
            # else: skip it. write stays where it is.

        return write

export function removeElement(nums: number[], val: number): number {
    // nums[0 .. write-1] always holds exactly the kept elements seen so far.
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== val) {
            // Keep it: put it in the next free slot of the answer.
            // write <= read, so we never overwrite an element we haven't read yet.
            nums[write] = nums[read];
            write++;
        }
        // else: skip it. write stays where it is.
    }
    return write;
}

Complexity

Time O(N)Space O(1)

One pass, each element is read once and written at most once. Only two integers of extra memory.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Copy the kept elements into an extra array, then copy them back	O(N)	O(N)
Optimal	read visits every element; write marks where the next kept element goes	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“remove … in place”No second array → we must reuse the front of `nums` as the output.
“return k, the first k elements are checked”The answer is a prefix `nums[0 … k−1]` → a `write` pointer that marks the end of that prefix.
“keep elements that are not val”A simple keep/skip decision per element → a `read` pointer that visits each one once.

Filter the array+in place+answer is the first k slots→Two Pointers (same direction: read / write)

This is the anchor of the read / write family. Both pointers start at 0 and move the same way (left to right). read moves every step; write moves only when we keep something. The keep rule here is the simplest possible: "is it not val?". The next questions keep exactly the same loop and only change that rule — "differs from the last written element" (Remove Duplicates), "is non-zero" (Move Zeroes), "differs from the element two slots back" (Remove Duplicates II).

Don't make this mistake

Pattern confusion: using opposite-end pointers by default

Two pointers does not always mean one at each end. Here both pointers start at 0 and walk right together — that is the read / write sub-pattern. (A swap-from-the-end version of this problem does exist and is also O(N), but it scrambles the order and is harder to get right. The read / write loop is the one that carries over to the next four questions.)

Pattern confusion: thinking this is a sliding window

There is no contiguous range we are measuring. The kept elements can be far apart in the input ([0, 1, _, _, 3, 0, 4, _]). We are filtering the array, not looking at a window. Nothing is ever "removed from the left" — write only moves forward.

Erasing inside the loop

✗ for (int i = 0; i < nums.size(); i++) if (nums[i] == val) nums.erase(nums.begin() + i);

✓ if (nums[read] != val) nums[write++] = nums[read];

Each erase shifts everything after it, so the loop is O(N²). Worse, after an erase the next element slides into index i and then i++ skips it — [2, 2] with val = 2 leaves one 2 behind.

Returning the wrong number

✗ return nums.size();

✓ return write;

We never shrink nums — the old values after slot k − 1 are still there. The answer is how many we kept, which is exactly write.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

Remove Duplicates from Sorted Array