Remove Element

Difficulty: Easy | Acceptance: 60.45% | Paid: No

Topics: Array, Two Pointers

• Examples
• Constraints
• Brute Force
• Two Pointers - Write Index
• Two Pointers - Swap to End

Examples

Input

nums = [3,2,2,3], val = 3

Output

2, nums = [2,2,_,_]

Input

nums = [0,1,2,2,3,0,4,2], val = 2

Output

5, nums = [0,1,4,0,3,_,_,_]

Constraints

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

Brute Force

Intuition

The most straightforward approach is to create a new array to store elements that are not equal to val. This is essentially building the result from scratch and returning its size.

Steps

• Initialize a new empty array to store the result.
• Iterate through the given array.
• For each element, if it’s not equal to the value we want to remove, add it to the result array.
• After iteration, copy the elements of the result array back to the original array.
• Return the size of the result array.

def removeElement(nums, val):
    result = []
    for num in nums:
        if num != val:
            result.append(num)
    for i in range(len(result)):
        nums[i] = result[i]
    return len(result)

Complexity

• Time: O(n), where n is the length of the array. We iterate through the array twice, once to build the result and once to copy it back.
• Space: O(n), because we use extra space to store the result array.

Two Pointers - Write Index

Intuition

We can solve this in-place by keeping track of where to write the next valid element. This way, we only need one pass through the array.

Steps

• Initialize a variable writeIndex to 0, which will keep track of the position where the next valid element should be written.
• Iterate through the array with a read pointer (the loop index).
• For each element, if it’s not equal to val, write it to the position indicated by writeIndex and increment writeIndex.
• After processing all elements, writeIndex will contain the count of elements that are not equal to val.
• Return writeIndex.

def removeElement(nums, val):
    writeIndex = 0
    for i in range(len(nums)):
        if nums[i] != val:
            nums[writeIndex] = nums[i]
            writeIndex += 1
    return writeIndex

Complexity

• Time: O(n), where n is the length of the array. We iterate through the array once.
• Space: O(1), because we only use a constant amount of extra space.

Two Pointers - Swap to End

Intuition

Another in-place approach involves moving elements that should be removed to the end of the array by swapping. This approach can reduce the number of assignments when the number of elements to remove is small.

Steps

• Initialize two pointers: left at the beginning (0) and right at the end (length - 1) of the array.
• While left is less than or equal to right, do the following:
• If the element at left is equal to val, swap it with the element at right and decrement right (since the element at right has now been moved to a position we will not scan again).
• If the element at left is not equal to val, increment left.
• Continue until left surpasses right.
• The new length of the array without val is right + 1.

def removeElement(nums, val):
    left, right = 0, len(nums) - 1
    while left <= right:
        if nums[left] == val:
            nums[left], nums[right] = nums[right], nums[left]
            right -= 1
        else:
            left += 1
    return right + 1

Complexity

• Time: O(n), where n is the length of the array. In the worst case, we might need to swap all elements to the end.
• Space: O(1), as we only use a constant amount of extra space.