Remove Element

easy array two pointers in-place

Problem

Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed.

Inputnums = [3, 2, 2, 3, 4, 3], val = 3

Output3, with nums starting [2, 2, 4, …]

Three 3's are removed; the kept values 2, 2, 4 fill the front in their original order.

nums (comma-separated)

val

def remove_element(nums, val):
    w = 0
    for r in range(len(nums)):
        if nums[r] != val:
            nums[w] = nums[r]
            w += 1
    return w

function removeElement(nums, val) {
  let w = 0;
  for (let r = 0; r < nums.length; r++) {
    if (nums[r] !== val) {
      nums[w++] = nums[r];
    }
  }
  return w;
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int w = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] != val) {
                nums[w++] = nums[r];
            }
        }
        return w;
    }
}

int removeElement(vector<int>& nums, int val) {
    int w = 0;
    for (int r = 0; r < nums.size(); r++) {
        if (nums[r] != val) {
            nums[w++] = nums[r];
        }
    }
    return w;
}

Explanation

The goal is to throw away every copy of a target value val while keeping the rest packed at the front. The neat way to do this without a second array is a slow-write, fast-read pointer pair.

The read pointer r visits every element. The write pointer w only moves forward when we keep something. So w always points at the next free slot for a survivor.

The rule is simple: if nums[r] != val, the element is a keeper, so we copy it to nums[w] and bump w. If it equals val, we skip it entirely and leave w where it is. Whatever sits past w at the end does not matter.

Example: nums = [3, 2, 2, 3, 4, 3], val = 3. The 3s are skipped; 2, 2, and 4 are copied to the front in order. We end with [2, 2, 4, ...] and return 3.

It is one pass over the array with only a couple of integer variables, so it runs in linear time using constant extra space.

Time: O(n) Space: O(1)