DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Remove Element

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 28

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe first k positions are the only part that matters

The operation does not need to physically shrink nums. It only needs to make its prefix correct: after the method returns k, positions 0 through k - 1 must contain every value different from val. Anything from position k onward is irrelevant, so overwriting unwanted values is enough to remove them logically.

Scan the array from left to right. Whenever you find a value that should remain, place it at the next unused position in the valid prefix. The scan pointer may be ahead of that position because it has passed over values equal to val, while the write pointer advances only when a value survives.

An array being compacted with a scan pointer and a write pointerDraw an array of indexed cells from left to right, with repeated cells containing val mixed among values that should remain. Place scan pointer i over the cell currently being examined and write pointer k at the next open position in the prefix. The scan pointer moves across every cell, while the write pointer stays still when i sees val and advances after copying another value. The front segment from index 0 through k - 1 is shaded as the valid result, making the compaction visible.472val9val5valvalid prefix: 0 .. k−101234567i scans every position →k = 3next writei = 5scanningval entries are skipped, not deletedi advances for every input; k advances only when a value differs from val

Approach

  1. Set k to 0 before scanning, because the valid prefix is empty and k must always identify the next position available for a surviving value.
  2. Visit each index i from 0 through nums.size() - 1, because every original element must be classified exactly once as either removed or retained.
  3. If nums[i] equals val, do nothing, because that value must not enter the first k positions and the next surviving value should reuse its space.
  4. If nums[i] does not equal val, write it to nums[k] and then increment k, because this appends one retained value to the compact prefix and reserves the following position.
  5. Return k after the scan, because k is exactly the count of values different from val and all those values have already been placed in positions 0 through k - 1.

Complexityone scan and constant working memory

MEASUREBOUNDWHY
TimeO(n)The loop reads each of the n original positions once. Each position takes one comparison and, for a survivor, one assignment, so no element is revisited or shifted repeatedly.
SpaceO(1) extraThe two integer indices use constant working memory, and the method modifies nums in place. The output prefix is excluded; even when every value equals val or no value equals val, the working storage remains constant.
Here n denotes nums.size(). The returned prefix is required output and is excluded from the extra-space bound.

Annotated solutionC++ · stable compaction · the simplest two-pointer form

CPPCopy each surviving value into the next position of the compact prefix.
#include <vector>

using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }

        return k;
    }
};

The important placement is nums[k++] = nums[i]. The read index i keeps moving through the original scan, while k moves only after a non-val value is accepted. When k is less than i, the assignment overwrites an earlier removed value; when k equals i, it simply writes the value back to its original position.

The swap-with-the-end alternativewhen changing the order can reduce unnecessary writes

Because the problem permits the surviving values to change order, you can replace a val at the current index with the element at the current end of the not-yet-processed region. Decrease the end immediately, but do not advance the scan pointer after the replacement: the moved value may also equal val and needs another check.

CPPReplace unwanted values with unchecked values from the shrinking suffix.
#include <vector>

using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = static_cast<int>(nums.size());
        int i = 0;

        while (i < k) {
            if (nums[i] == val) {
                nums[i] = nums[k - 1];
                --k;
            } else {
                ++i;
            }
        }

        return k;
    }
};

This is a different arrangement rather than a better asymptotic bound: time remains O(n) and extra space remains O(1). It can perform fewer assignments when many values equal val, but it does not preserve the order of survivors. The stable compaction version is usually easier to reason about; this version is useful when order is explicitly irrelevant and avoiding writes matters.

Common mistakestwo wrong pointer updates that look almost correct

Previous · Remove Duplicates from Sorted Array