# Remove Element
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-element)
Canonical: https://scaleengineer.com/dsa/problems/remove-element
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
Given an integer array `nums` and an integer `val`, remove all occurrences of `val` in `nums` [**in-place**](https://en.wikipedia.org/wiki/In-place%5Falgorithm). The order of the elements may be changed. Then return _the number of elements in_ `nums` _which are not equal to_ `val`.

Consider the number of elements in `nums` which are not equal to `val` be `k`, to get accepted, you need to do the following things:

* Change the array `nums` such that the first `k` elements of `nums` contain the elements which are not equal to `val`. The remaining elements of `nums` are not important as well as the size of `nums`.
* Return `k`.

**Custom Judge:**

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be **accepted**.

**Example 1:**

**Input:** nums = [3,2,2,3], val = 3
**Output:** 2, nums = [2,2,_,_]
**Explanation:** Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

**Example 2:**

**Input:** nums = [0,1,2,2,3,0,4,2], val = 2
**Output:** 5, nums = [0,1,4,0,3,_,_,_]
**Explanation:** Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

**Constraints:**

* `0 <= nums.length <= 100`
* `0 <= nums[i] <= 50`
* `0 <= val <= 100`

# Approaches
## Two Pointers - Slow and Fast
This approach uses two pointers, a "slow" pointer and a "fast" pointer, to iterate through the array. The fast pointer scans the array, and when it finds an element that should be kept (i.e., not equal to `val`), it copies that element to the position indicated by the slow pointer. The slow pointer only advances when a valid element is found and copied.
**Time:** O(n) · **Space:** O(1)
**Pros:** In-place modification, satisfying the O(1) space complexity requirement.; Simple and intuitive to understand.; Preserves the relative order of the elements that are not removed.
**Cons:** May perform unnecessary copy operations. For example, if `val` is not present in the array, every element is copied over itself. The number of writes is equal to the number of elements to keep, which can be up to `n`.
### Explanation
We can think of the array as being split into two parts by the slow pointer `k`. The elements before `k` (i.e., `nums[0...k-1]`) are the processed elements that are not equal to `val`. The elements at or after the fast pointer `i` are the ones we haven't yet examined.

We initialize a slow pointer, `k`, to 0. We iterate through the array with a fast pointer, `i`, from the beginning to the end. For each element `nums[i]`, if it's not equal to `val`, we copy it to `nums[k]` and then increment `k`. This effectively overwrites any `val` elements with subsequent non-`val` elements. After the loop, `k` is the new length of the array.

This method is advantageous because it preserves the relative order of the elements that are kept.

```java
class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // Slow pointer indicates the next position to insert a non-val element.
        // Fast pointer 'i' iterates through the array.
        for (int i = 0; i < nums.length; i++) {
            // If the current element is not the one to be removed...
            if (nums[i] != val) {
                // ...copy it to the slow pointer's position.
                nums[k] = nums[i];
                // Move the slow pointer to the next position.
                k++;
            }
        }
        // 'k' is the count of elements not equal to 'val'.
        return k;
    }
}
```
### Algorithm
- Initialize a slow pointer, `k`, to 0. This pointer will keep track of the next position to place an element that is not equal to `val`.
- Iterate through the array with a fast pointer, `i`, from the beginning to the end.
- For each element `nums[i]`:
    - If `nums[i]` is not equal to `val`, we consider it a valid element.
    - We copy this valid element to the position of the slow pointer: `nums[k] = nums[i]`.
    - We then increment the slow pointer `k` to prepare for the next valid element.
- After the loop finishes, `k` represents the number of valid elements, which is the new length of the modified array. The first `k` elements of `nums` now contain all the elements from the original array except for `val`.

## Two Pointers - Optimized for Few Removals
This approach also uses two pointers but in a different way. One pointer `i` starts from the beginning, and another pointer `n` represents the effective end of the array. When an element to be removed is found at `nums[i]`, it's replaced by the last element of the effective array (`nums[n-1]`), and the effective size `n` is reduced. This minimizes the number of element-moving operations.
**Time:** O(n) · **Space:** O(1)
**Pros:** In-place modification with O(1) space complexity.; Highly efficient in terms of write operations. The number of assignments is equal to the number of elements removed, which is optimal. This is beneficial when elements to remove are rare.
**Cons:** The relative order of the remaining elements is not preserved, which might be a drawback for a different problem variation.
### Explanation
This method is particularly efficient when the number of elements to remove is small. We maintain two pointers. One pointer `i` starts from the beginning, and a variable `n` represents the effective size of the array, initialized to its full length.

We iterate with `i` as long as `i < n`. When we encounter an element `nums[i]` that equals `val`, we swap it with the last element of the effective array, `nums[n-1]`, and then decrement `n`. We do not increment `i` because the new element at `nums[i]` (the one we just swapped in) needs to be processed. If `nums[i]` is not equal to `val`, we simply increment `i` to move to the next element.

The number of assignments (writes) is equal to the number of elements we remove. This is better than the previous approach where the number of writes was equal to the number of elements we keep.

```java
class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                // Replace the element to remove with the last element
                nums[i] = nums[n - 1];
                // Decrease the effective array size
                n--;
            } else {
                // Move to the next element
                i++;
            }
        }
        return n;
    }
}
```
### Algorithm
- Initialize a pointer `i = 0` and a variable `n` to `nums.length`.
- Loop while `i < n`.
- If `nums[i]` is equal to `val`:
    - Replace `nums[i]` with the last valid element `nums[n - 1]`.
    - Decrement `n` to shrink the effective array size.
- Else (if `nums[i]` is not equal to `val`):
    - Increment `i` to move to the next element.
- After the loop, return `n`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int k = 0;
        foreach(int x in nums) {
            if (x != val) {
                nums[k++] = x;
            }
        }
        return k;
    }
}
```

### Java

```java
class Solution {
public
  int removeElement(int[] nums, int val) {
    int k = 0;
    for (int x : nums) {
      if (x != val) {
        nums[k++] = x;
      }
    }
    return k;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} val * @return {number} */ var removeElement =
  function (nums, val) {
    let k = 0;
    for (const x of nums) {
      if (x !== val) {
        nums[k++] = x;
      }
    }
    return k;
  };

```

### CPP

```cpp
class Solution {
public:
  int removeElement(vector<int> &nums, int val) {
    int k = 0;
    for (int x : nums) {
      if (x != val) {
        nums[k++] = x;
      }
    }
    return k;
  }
};

```

### Python

```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int: k = 0 for x in nums: if x != val: nums[k] = x k += 1 return k

```