Problem Solving - Arrays

You can find the question here

Welcome! In our previous session, we explored various aspects of arrays, including their types, array slicing, and the computational costs associated with array operations. In this article, we will put our newfound knowledge to the test by solving a problem using Python.

The question at hand involves the removal of all occurrences of a specific number 'val' from an array, while also efficiently filling any resulting gaps without creating a new array. We will explore two different approaches to tackle this problem. The first approach is relatively simple, while the second one is slightly more intricate.

1st Method (remove() function)

    def removeElement(self, nums: List[int], val: int) -> int:

        while val in nums:
            nums.remove(val)
        return len(nums)

The above solution entails traversing the array and removing the first occurrence of the value 'val' whenever encountered. Following the removal, the subsequent number is shifted to fill the vacated space. However, this method incurs certain costs due to the removal operation.

2nd Method (two pointer)

In our exploration of two different methods to solve the problem, the second approach focuses on achieving a solution without incurring any additional time costs. We will delve into this alternative method, which ensures efficient removal of 'val' without compromising time efficiency.

    def removeElement(self, nums: List[int], val: int) -> int
        t= 0
        i=0

        while i < len(nums):
            if nums[i] != val:
                nums[t] = nums[i]
                t +=1
            i += 1

        return t

The second solution employs a two-pointer approach. One pointer traverses the array, while the other pointer is only updated when a value different from 'val' is encountered. The first pointer, 'i', increments at each iteration, while the second pointer, 't', only increases when a non-'val' value is found. By returning the value of 't', we obtain the count of non-'val' values in the array.

Time and Space Complexities

In summary, we have analyzed both methods for solving the problem. The first method involves removing occurrences of 'val' from the array, resulting in a time complexity of O(nk) where k is the length of the array after val was deleted and the shifting of elements ocurred. On the other hand, the second method utilizes a two-pointer approach with a time complexity of O(n), as it only requires traversing the array once and performing constant-time operations.

In terms of space complexity, both methods exhibit constant space utilization, denoted as O(1), as all operations are performed in-place within the given array.

Throughout our exploration, we have gained insights into array traversal, element removal, and the implications of these operations on time and space complexity.

Thank you for joining us, and see you in our next session.