Remove Element — Editorial

Opening the reading…

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.

Approach

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.

Visit each index i from 0 through nums.size() - 1, because every original element must be classified exactly once as either removed or retained.

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.

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.

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

MEASURE	BOUND	WHY
Time	O(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.
Space	O(1) extra	The 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.