Leetcode 27. Remove Element

Problem

Leetcode 27 - Remove Element

Example:

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).

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).

Approach

Since the question states that “It does not matter what you leave beyond the returned k” for the nums array, we can initialize the k to 0 then increment everytime we encounter an element that is not equal to the val. Meaning that once we encounter an element, we should put that element in nums[k], then increment the k value. Once we are done iterating through the array, we can simply return the k.

Visualization of the Appraoch:

val = 3

nums = [3, 2, 2, 3]
k = 0

Since nums[0] == 3, we can ignore

Since nums[1] != 3, we put it in k then increment k by 1
nums = [2, 2, 2, 3]
k = 1

Since nums[2] != 3, we put it in k then increment k by 1
nums = [2, 2, 2, 3]
k = 2

Since nums[3] == 3, we can ignore

Thus k = 2, we do not care about rest of the array as in the question it states that "It does not matter what you leave beyond the returned k"

Here is the Python code for the solution:

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

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

Time Complexity and Space Complexity

Time Complexity: $O(n)$ since we are iterating through the list.

Space Complexity: $O(1)$ since we aren’t using any extra space.