Problem Statement in English

You’re given an integer array nums and an integer val. You need to remove all occurrences of val in nums in-place. The relative order of the elements may be changed. After removing the elements, return the new length of the array.

Approach

Similar to LeetCode 26. Remove Duplicates from Sorted Array, we can use a two-pointer approach to solve this problem. Instead of checking for duplicates, we will check for the value val and skip it. We will maintain a pointer k to keep track of the position where we can place the next valid element.

And we’re done!

Solution in Python


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0

        for i in range(len(nums)):
            if val != nums[i]:
                nums[k] = nums[i]
                k += 1
        
        return k

Complexity

  • Time: $O(n)$
    Since we are iterating through the entire array once, the time complexity is linear.

  • Space: $O(1)$
    Since we are not using any extra space, the space complexity is constant.

And we are done.