[Leet Code] 27.Remove Element - Easy

문제

 

Description

Input: nums => list[int], val => int

 Remove all elements same with "val" in the given array "nums" and change the array to starts with the elements which are not same with "val". The array must be changed in place.

 Return the number of elements same with "val".

 The judge will test below two points:

    1. The returned value is correct - name this value as "k"

    2. Each element from 0 to "k"-1 in the array "nums" isn't same with "val"

 

How to solve

Since we need to check all elements, the TC can't be faster than O(n). So I choose to check the element one by one from index 0.

There are 2 cases:

• The selected element isn't same with "val" : we can move on to the next element
• The selected element is same with "val": we need to remove the element

There are 2 ways to remove the elements - remove it (The length of the array will be changed) or replace it to another integer. We simply can replace the element to the last element of the array - which we didn't check yet if it's same with "val" or not - since the order of non-"val" values which have to left in the array once the function finished doesn't matter. After that, we need to mark that the last value doesn't need to be checked.

 

Code

def removeElement(nums: List[int], val: int) -> int:
    p1, p2 = 0, len(nums)-1
    while p1 <= p2:
        if nums[p1] != val:
            p1+=1
            continue
        nums[p1] = nums[p2]
        p2-=1
    return p1

TC O(n) / SC O(1)