# 27. Remove Element

LeetCode Problem Link (opens new window)

You are given an array nums and a value val, you need to remove all instances of that value in place and return the new length of the array.

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. You don't need to consider elements beyond the new length of the array.

Example 1: Given nums = [3,2,2,3], val = 3, Your function should return length 2, with the first two elements of nums being 2. You do not need to consider elements beyond the new length of the array.

Example 2: Given nums = [0,1,2,2,3,0,4,2], val = 2, Your function should return length 5, with the first five elements of nums being 0, 1, 3, 0, 4.

You do not need to consider elements beyond the new length of the array.

# Thought Process

Some might think that simply deleting the elements would suffice.

Remember that the elements of an array are contiguous in memory, making it impossible to delete an individual element; you can only overwrite it.

For more about array basics, refer to Array Theory Basics (opens new window).

# Brute Force Approach

A brute force solution involves using two nested loops: one to iterate through the array elements and another to update the array.

Deletion can be illustrated as follows:

Brute Force Approach for Removing Element

Clearly, the time complexity of the brute force solution is O(n²), but it can still pass in LeetCode.

Here's the code for the brute force approach:

// Time Complexity: O(n²)
// Space Complexity: O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // Element to be removed found, shift array elements forward
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // Because elements after index i were moved forward, decrement i
                size--; // Reduce array size
            }
        }
        return size;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

# Two-Pointer Approach

Two-pointer technique (fast and slow pointers): This achieves the objective of two loops in a single loop using a fast and slow pointer.

Define fast and slow pointers:

Fast Pointer: Searches for new array elements; the new array excludes the target element.
Slow Pointer: Points to the position where the new array's elements are to be updated.

Not understanding what the fast and slow pointers represent is a common source of confusion. Understanding their roles makes the rest of the thought process easier.

Deletion can be illustrated as follows:

Two-Pointer Approach for Removing Element

It's common to encounter the two-pointer technique (fast and slow pointers) in array and linked list problems; many interview questions involving arrays, linked lists, and strings use this technique.

Here is the code for the two-pointer approach:

// Time Complexity: O(n)
// Space Complexity: O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Note that these implementations do not change the relative order of elements!

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

# Versions in Other Languages

# Java:

class Solution {
    public int removeElement(int[] nums, int val) {
        // Brute Force Method
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < n; j++) {
                    nums[j - 1] = nums[j];
                }
                i--;
                n--;
            }
        }
        return n;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int removeElement(int[] nums, int val) {
        // Fast and Slow Pointers
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

// Two-Pointer Approach from Opposite Ends
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; // Move right to first non-val from the end
        while(left <= right) {
            if(nums[left] == val) { // Need to remove element at left
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// Two-Pointer Approach from Opposite Ends (Version 2)
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Python:

# Fast and Slow Pointer Approach
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast = 0
        slow = 0
        size = len(nums)
        while fast < size:
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

1
2
3
4
5
6
7
8
9
10
11
12

# Brute Force Method
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, l = 0, len(nums)
        while i < l:
            if nums[i] == val:
                for j in range(i+1, l):
                    nums[j-1] = nums[j]
                l -= 1
                i -= 1
            i += 1
        return l

1
2
3
4
5
6
7
8
9
10
11
12

# Two-Pointer Approach from Opposite Ends
# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            while left <= right and nums[left] != val:
                left += 1
            while left <= right and nums[right] == val:
                right -= 1
            if left < right:
                nums[left] = nums[right]
                left += 1
                right -= 1
        return left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Go:

// Brute Force Method
// Time Complexity: O(n²)
// Space Complexity: O(1)
func removeElement(nums []int, val int) int {
    size := len(nums)
    for i := 0; i < size; i++ {
        if nums[i] == val {
            for j := i + 1; j < size; j++ {
                nums[j-1] = nums[j]
            }
            i--
            size--
        }
    }
    return size
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// Fast and Slow Pointers
// Time Complexity: O(n)
// Space Complexity: O(1)
func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

1
2
3
4
5
6
7
8
9
10
11
12
13

// Two-Pointer Approach from Opposite Ends
func removeElement(nums []int, val int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        for left <= right && nums[left] != val {
            left++
        }
        for left <= right && nums[right] == val {
            right--
        }
        if left < right {
            nums[left] = nums[right]
            left++
            right--
        }
    }
    return left
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# JavaScript:

// Time Complexity: O(n)
// Space Complexity: O(1)
var removeElement = (nums, val) => {
    let k = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] != val){
            nums[k++] = nums[i]
        }
    }
    return k;
};

1
2
3
4
5
6
7
8
9
10
11

# TypeScript:

function removeElement(nums: number[], val: number): number {
    let slowIndex: number = 0, fastIndex: number = 0;
    while (fastIndex < nums.length) {
        if (nums[fastIndex] !== val) {
            nums[slowIndex++] = nums[fastIndex];
        }
        fastIndex++;
    }
    return slowIndex;
};

1
2
3
4
5
6
7
8
9
10

# Ruby:

def remove_element(nums, val)
    i = 0
    nums.each_index do |j|
        if nums[j] != val
            nums[i] = nums[j]
            i+=1
        end
    end
    i
end

1
2
3
4
5
6
7
8
9
10

# Rust:

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut slowIdx = 0;
        for pos in (0..nums.len()) {
            if nums[pos]!=val {
                nums[slowIdx] = nums[pos];
                slowIdx += 1;
            }
        }
        return (slowIdx) as i32;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

# Swift:

func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
    var slowIndex = 0

    for fastIndex in 0..<nums.count {
        if val != nums[fastIndex] {
                nums[slowIndex] = nums[fastIndex]
                slowIndex += 1
        }
    }
    return slowIndex
}

1
2
3
4
5
6
7
8
9
10
11

# PHP:

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $val
     * @return Integer
     */
    function removeElement(&$nums, $val) {
        if (count($nums) == 0) {
            return 0;
        }
        // Fast and Slow Pointers
        $slow = 0;
        for ($fast = 0; $fast < count($nums); $fast++) {
            if ($nums[$fast] != $val) {
                $nums[$slow] = $nums[$fast];
                $slow++;
            }
        }
        return $slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# C:

int removeElement(int* nums, int numsSize, int val){
    int slow = 0;
    for(int fast = 0; fast < numsSize; fast++) {
        if(nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

1
2
3
4
5
6
7
8
9

# Kotlin:

fun removeElement(nums: IntArray, `val`: Int): Int {
    var slowIndex = 0
    for (fastIndex in nums.indices) {
        if (nums[fastIndex] != `val`) nums[slowIndex++] = nums[fastIndex]
    }
    return slowIndex
}

1
2
3
4
5
6
7

# Scala:

object Solution {
  def removeElement(nums: Array[Int], `val`: Int): Int = {
    var slow = 0
    for (fast <- 0 until nums.length) {
      if (`val` != nums(fast)) {
        nums(slow) = nums(fast)
        slow += 1
      }
    }
    slow
  }
}

1
2
3
4
5
6
7
8
9
10
11
12

# C#:

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.Length; fast++) {
            if (val != nums[fast]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# Dart:

int removeElement(List<int> nums, int val) {
    var left = 0;
    var right = nums.length - 1;
    while (left <= right) {
        if (nums[left] == val) {
            while (nums[right] == val&&left<=right) {
                right--;
            if (right < 0) {
                return 0;
        }
      }
      nums[left] = nums[right--];
    } else {
      left++;
    }
  }
  return left;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

← 2. Binary Search 4. Squares Of A Sorted Array →

# 27. Remove Element

# Thought Process

# Brute Force Approach

# Two-Pointer Approach

# Related Problems

# Versions in Other Languages

# Java:

# Python:

# Go:

# JavaScript:

# TypeScript:

# Ruby:

# Rust:

# Swift:

# PHP:

# C:

# Kotlin:

# Scala:

# C#:

# Dart: