[Top Interview 150] 27. Remove Element

Solution)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        res = 0
        left, right = 0, len(nums)-1

        while left <= right:
            if nums[left] == val and nums[right] != val:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
                res += 1

            elif nums[left] != val and nums[right] == val:
                left += 1
                right -= 1
                res += 1

            elif nums[left] != val and nums[right] != val:
                left += 1
                res += 1

            else:
                right -= 1
        
        return res

 

Time Complexity: Probably O(n)?

Space Complexity: O(1)

 

Problem: LeetCode

Explanation)

Even though there is a very convenient method for removing a value called "remove()", but the time complexity for using that method would be too big as the method iterates through the list to find the value to remove.

 

So instead, we will be using two pointers.

Left pointer will look for an element that has the same value as val.

Right pointer will look for an element that has a differen value.

 

If such condition is met, then we will swith those elements so that all the elements with the value of val will be at the end of nums.

Initialization)

We will have a variable that will count how many elements don't have the value val.

 

Then initialize left pointer to 0 and right pointer to len(nums) - 1.

This allows us to start from both ends of nums.

 

def removeElement(self, nums: List[int], val: int) -> int:
        res = 0
        left, right = 0, len(nums)-1

4 Conditions)

We have 4 conditions to consider.

1) Only left has the value val

2) Only right has the value val

3) Both left and right don't have the value val

4) Both left and right have the value val

 

To have all the elements with value val to be at the end of nums, we obviously want the condition 1. Because then we can switch left and right.

 

 

condition 1

 

The rest of the conditions are merely steps of adjusting the lists so that we can eventually reach condition 1.

 

condition 2

 

condition 3

 

condition 4

To find how many elements don't have the value val, we're going to add 1 to res whenever we are in the condition where one of the pointer's element doesn't have the value val. This means that we will add one to the res in conditions 1, 2, 3.  

 

def removeElement(self, nums: List[int], val: int) -> int:
        res = 0
        left, right = 0, len(nums)-1

        while left <= right:
            if nums[left] == val and nums[right] != val:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
                res += 1

            elif nums[left] != val and nums[right] == val:
                left += 1
                right -= 1
                res += 1

            elif nums[left] != val and nums[right] != val:
                left += 1
                res += 1

            else:
                right -= 1
        
        return res

 

I'm not entirely sure what happened with Top Interview Questions section. I guess I'll hop on to Top Interview 150 instead which seems to be very similar. I watched NeetCode's recent video of him leaving Google to solve more LeetCode problems. I simply cannot understand how he enjoys solving LeetCode haha.

 

Thank you for visiting my blog and please let me know if you have any quesitons :)