Simple Python O(n) two pointer in place solution


  • 16
    S

    Starting from the left every time we find a value that is the target value we swap it out with an item starting from the right. We decrement end each time as we know that the final item is the target value and only increment start once we know the value is ok. Once start reaches end we know all items after that point are the target value so we can stop there.

      def removeElement(self, nums, val):
        start, end = 0, len(nums) - 1
        while start <= end:
            if nums[start] == val:
                nums[start], nums[end], end = nums[end], nums[start], end - 1
            else:
                start +=1
        return start

  • 1

    How can you be sure that nums[end] !=val? If not, it should now swap those two values.


  • 0
    S

    It's true that nums[end] could equal val, but notice we only increment start if nums[start] is not equal val, so on the next iteration we will swap the value out for end -1 val now. You could imagine the path for val going from end to start to end -1 to start to end-2 as long as all the end values continue to be equal to val.


  • 0
    Z

    @softray I'm wondering why this doesn't work:

    nums[end],nums[start],end=nums[start],nums[end],end-1


  • 0
    S

    That should work if all you did was swap your line with the one below in the code:

    nums[start], nums[end], end = nums[end], nums[start], end - 1


  • 0
    X

    sorry, i just don't understand why you return start? why's start a list?


  • 0
    F

    I understand that you get the right number of non-matched items, but where did you remove the matched values from nums?
    How can it return [2,2] from [3,2,2,3], 3 when I run it?


  • 0
    S

    In order to modify the list you should add line nums[:] = nums[:start] at the end - it will remove all val values from the list. But thats require extra space at this point - nums[:start]

        def removeElement(self, nums, val):
            start, end = 0, len(nums) - 1
            while start <= end:
                if nums[start] == val:
                    nums[start], nums[end], end = nums[end], nums[start], end - 1
                else:
                    start +=1
            nums[:] = nums[:start]
            return start
    

  • 0
    W

    @Smosker this problem only requires to return the length of these remian numbers, and it doesn't matter the old value left beyond the new length


  • 0
    F
    This post is deleted!

  • 0
    B
    This post is deleted!

  • 1
    B

    here is my return sorted solution

    def removeElement(self, nums, val):
      
            start, end = 0, len(nums)-1 
            f=0
            while start <=end:
                if nums[start] == val:
                    start+=1
                elif nums[end]==val:
                    end-=1
                else:
                    nums[f]=nums[start]
                    f+=1
                    start+=1
            return f
    

  • 0
    D

    @xz137

    
           """
           :type nums: List[int]
           :type val: int
           :rtype: int
           """
    

  • 0
    D

    @softray nice!


  • 6
    G

    @softray I use nums.remove() to remove the value

    class Solution(object):
        def removeElement(self, nums, val):
            for i in range(nums.count(val)):
                nums.remove(val)
            return len(nums)
                
    

  • 1
    J

    @Gene20 remove() needs to find the value, which is less efficient than using the index. I use pop() instead:

    class Solution(object):
        def removeElement(self, nums, val):
            """
            :type nums: List[int]
            :type val: int
            :rtype: int
            """
            i, total = 0, len(nums)
            while i < total:
                if nums[i] == val:
                    nums.pop(i)
                    total -= 1
                else:
                    i += 1
            return len(nums)
        
    

  • 0
    B

    @jesse4 I believe neither pop or remove could be used since the question asks for an "in place" solution.


  • 0
    J

    @BeeFarmer Isn't remove and pop in place?


  • 0
    B

    @jesse4 You are right. I misunderstood the definition of "in place". It is ok to use them!
    However, since the question mentions that "The order of elements can be changed. It doesn't matter what you leave beyond the new length", it tends to ask you to manipulate the list (swapping or reassigning values) instead of getting rid of partial values (removing or deleting values) lol! Thanks.


  • 1
    K

    @jesse4 Wow! What a coincidence. My solution is exactly the same as this :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.