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

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

Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode

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! 🙂

原文链接：Comparating Hash Tables, Two Pointers, and In-Place Algs for Removing Duplicates