[LeetCode Solution] 27. Remove Element

Problem Description

LeetCode 27. Remove Element

Algorithm to remove the specified value (val) from the list and determine the remaining number of elements.

Solution

Approach 1.

1) Traverse nums as long as val is present in nums. 2) Remove and simultaneously append “_” to the end of the list. 3) Increment cnt for each discovery and return the difference from the original length.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        org_len = len(nums)
        cnt = 0
        while val in nums:
            nums.remove(val)
            nums.append("_")
            cnt += 1
        return org_len - cnt

The time and space complexity of the above solution are as follows:

• Time Complexity: O(N^2)
  • The time complexity of the remove function is O(N), and since this is repeated for the number of elements in nums, the overall time complexity is O(N^2).
• Space Complexity: O(1)
  • Only a few simple variables are used, resulting in O(1) space complexity.

This approach has a time complexity of O(N^2), so as the input size increases, the execution time may become long, with a high likelihood of timeout.

Approach 2. Two Pointer

Used Two Pointer to adjust two indices, left and right, while removing duplicate values. 1) Initialize left and right indices from 0, 2-1) If right is val, convert it to “_” and move right one step to the right. 2-2) If right is not val, swap left and right, and move both one step at a time.

Following this logic, assuming we remove 3 from the input 3223, the flow would be as follows:

3223
_223    <- Since right is 3, change it to _ and move right one step to the right
2_23    <- Since left and right are different
22_3    <- Swap the two values
22__    <- Since right is 3, change it to _

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left, right = 0, 0
        while right < len(nums):
            if nums[right] == val:
                nums[right] = '_'
                right += 1
            else: 
                nums[left], nums[right] = nums[right], nums[left]
                left += 1 
                right += 1
        return left

• Time Complexity: O(N)
  • It takes time proportional to the size of nums.
• Space Complexity: O(1)
  • Only a few simple variables are used, resulting in O(1) space complexity.