Comparating Hash Tables, Two Pointers, and In-Place Algs for Removing Duplicates

The "Remove Duplicates from Sorted Array" problem's 3 distinct techniques

In-place algorithms, two pointers, and hash tables are the focus today. Let's compare the benefits and drawbacks of each approach to determine which one is better.

Talk is cheap, show me the (python) code

1. Code for Hash Table approach

def removeDuplicates(nums):
    # Create an empty hash set
    num_set = set()
    # Iterate through the list
    for i in range(len(nums)):
        # If the current number is not in the set, add it
        if nums[i] not in num_set:
            num_set.add(nums[i])
    # Replace the original list with the unique elements from the set
    nums[:] = list(num_set)
    return len(nums)

👉 Explanation: In this method, the input list's unique components are stored in a hash set. We go through the list repeatedly, adding each item to the set. It won't be added if the element already exists in the set. We then return the length of the new list after replacing the original list with the set's unique items.

2. Code for Two Pointers approach

def removeDuplicates(nums):
    # Initialize pointers
    i = 0
    j = 1
    # Iterate through the list
    while j < len(nums):
        # If the current element is not equal to the previous element
        if nums[i] != nums[j]:
            # Move the pointer and update the current element
            i += 1
            nums[i] = nums[j]
        # Move to the next element
        j += 1
    return i + 1

👉 Explanation: The input list is iterated through using two pointers, i and j, in this method. The pointer j is used to cycle through the remaining elements of the list while the pointer i retains track of the last unique entry. We change the pointer i and update the current element if the current element is not equal to the preceding element. By adding 1 to the final value of i, we finally return the updated length of the list.

3. Code for In-Place Algorithm

def removeDuplicates(nums):
    # Initialize a pointer
    i = 0
    # Iterate through the list
    for j in range(1, len(nums)):
        # If the current element is not equal to the previous element
        if nums[j] != nums[i]:
            # Move the pointer and update the current element
            i += 1
            nums[i] = nums[j]
    return i + 1

👉 Explanation: This strategy is comparable to the Two Pointers strategy, except it eliminates duplicates using an in-place technique. To loop through the list and look for duplicates, we utilize a single pointer, i. We change the pointer and update the current element if the current element is not equal to the preceding element. By adding 1 to the final value of i, we finally return the updated length of the list.

⏱️ All of these approaches have the same time complexity O(n) and space complexity O(1) except for the Hash Table approach that have a space complexity O(n).

Hope you like reading! :)