Problem Definition

LeetCode Link: 27. Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. 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

Thought Process

The important point of this problem is The elements of an array are contiguous in memory addresses, and a specific element in the array cannot be deleted individually; it can only be overwritten.

Brute Force

The brute force solution to this problem is two nested for loops, where one for loop iterates through the array elements and the second for loop updates the array.

It is clear that the time complexity of the brute force solution is O(n^2), and this problem can pass the LeetCode with a brute force approach.

The code is as follows:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, l = 0, len(nums)
        while i < l:
            if nums[i] == val: # Find nodes that equal the target value.
                for j in range(i+1, l): # Remove the element and shift the subsequent elements forward.
                    nums[j - 1] = nums[j]
                l -= 1
                i -= 1
            i += 1
        return l
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

Two-pointer (Fast and Slow)

Two-pointer technique (fast and slow pointer method): It uses a fast pointer and a slow pointer to complete the work of two nested for loops within a single for loop.

Definition of Fast and Slow Pointers

• Fast Pointer: Used to find elements for the new array, which excludes the target element.

• Slow Pointer: Points to the position where the new array’s index is updated.

The two-pointer technique (fast and slow pointer method) is very common in operations involving arrays and linked lists. Many interview questions that test operations on arrays, linked lists, and strings utilize this approach.

The code is as follows:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast = 0  # fast pointer
        slow = 0  # slow pointer
        size = len(nums)
        while fast < size:  # The equality is not included because when a == size, accessing nums[a] would result in an out-of-bounds (out of range) error.
            # The slow pointer is used to collect values that are not equal to val. If the value at the fast pointer is not equal to val, it will be swapped with the value at the slow pointer.
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

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

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

Two-pointer (Left and Right)

This new solution introduces a variation of the two-pointer technique, but instead of using fast and slow pointers moving in one direction, it uses left and right pointers that traverse the array from opposite ends. The key idea is to swap elements from the left and right sides when necessary to efficiently remove the target value from the array.

In this approach, two pointers are initialized:

• Left Pointer: Starts from the beginning of the array.

• Right Pointer: Starts from the end of the array.

The idea is to:

1. Move the left pointer forward until it finds an element equal to val.

2. Move the right pointer backward until it finds an element that is not equal to val.

3. Swap the elements at the left and right pointers if the left pointer is still less than the right pointer. After swapping, increment the left pointer and decrement the right pointer to continue the process.

4. Repeat the process until the left pointer surpasses the right pointer.

This ensures that all elements that are not equal to val are shifted towards the beginning of the array. The function returns the position of the left pointer, which indicates the number of elements that are not equal to val.

The code is as follows:

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
  • Time Complexity: O(n)
  • Space Complexity: O(1) Related Problems