Day-6 Remove Element

This problem statement is from Leetcode's Introduction to Data Structures - Array 101. Under the sub-heading deleting items from an array.

Problem Statement

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Learnings from unsuccessful approaches

1. Keep in mind that the solution needs to be an in-place solution. And directly removing the given value from the original array would mean the length of the array getting changed. This would lead to unexpected results.
2. To get over the above-mentioned shortcoming. Keep a track of count of values removed. The number of removes and appends should be equal.
3. Removing an element by doing nums.remove(nums[x]), followed by doing nums.append(nums[x]) would lead to list index out of range error. As the positioning of elements has got changed after removing.

Solution Approach

1. Iterate over the original array.
2. Find the count of values in the original array.
3. Initialize the counter to 0.
4. Check if value of element is equal to val. If the condition is true. Store the value of the element. Remove the element. Followed by append. And keep incrementing the counter.
5. If the value of count and counter is the same. Break the loop.
6. Consider only the values excluding the appends. Return the resulting length.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        count = nums.count(val)  # Returns total count of val in original array
        counter = 0 # Initialized a counter to 0
        for x in range(0, len(nums)):
            if nums[x] == val:
                element = nums[x]
                nums.remove(nums[x])
                nums.append(element)
                counter += 1 #calculates the count of val's removed and appended at end
            if counter == count: 
                break
        return len(nums[0:len(nums)-count])

More learnings

1. The time complexity of the given solution is O(n^2). Remove method used inside the loop is expensive. Having complexity of O(n). I need to replace remove with a more efficient method/logic.
2. Time complexity
   • complexity of append - O(1)
   • complexity of length - O(1)
   • complexity of slice - O(n)
   • complexity of remove - O(n)

Solution by removing expensive List.remove()

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        count = 0

        if nums:
            for x in range(0, len(nums)):
                if nums[x] != val:
                    nums[index] = nums[x]
                    index += 1
                else:
                    count += 1
            while x > index:
                nums[index] = val
                index += 1
            return len(nums[:len(nums) - count])
        else:
            return 0

Learning

1. By scraping off List.remove() we are able to reduce the time complexity from O(n^2) to O(n).