Eliminating Duplicates: A Guide to Removing Duplicates from a Sorted Array

A new week, new challenges, and new algorithms to tackle and most importantly, understand. The algorithm we will be looking at, is an algorithm that allows one to delete duplicate elements from an already sorted array.
The algorithm in question is considered to be an easy one compared to the Dutch Flag Partitioning, which looked easy with the detailed explanation, but the reason for the difficulty being during whiteboard sessions (will update the entries with them soon) where you mix the pointer values in terms of greater, lesser and equality.
Anyhoo, let's get started with this one.

The Question

See leetcode question 26

Naive/Brute-force Approach

Obviously, there is a naive approach for this, and the plus side is its Space complexity is O(1).

Explanation/Thought Process

• assign a variable to represent the length of the array
• iterate through the array
  • use another loop to iterate from the next index to the end of the array
    • if the element from the first loop matches the element of the second loop
    • delete the matching element found
    • decrement the length of the array by one (we do this to cover for the missing element or we will get errors or wrong values)
• print the array (for visuals)
• return the length of the array

delDups.py

#!/usr/bin/env python3
def delDups(arr):
    n = len(arr)

    for i in range(n):
        for j in range(i + 1, n - 1):
            if arr[i] == arr[j]:
                del arr[j]
                n -= 1
    return n

test_delDup.py

#!/usr/bin/env python3
from delDups import delDups

arr = [1, 2, 2, 3, 4, 4, 5]
dups = delDups(arr)
print(arr[:dups])

result:

5
[1, 2, 3, 4, 5]

Problem With This Solution

While it fulfills the Space complexity of O(1), the Time complexity is O(n^2), which is the result of using two nested loops which take O(n) time to iterate through the array and O(n) time for comparisons for each iteration. And by this Big O notation graph I got, it is terrible.

Better Approach and Optimal Solution

There is a better approach that takes O(n) time to sort the array, removes duplicates, and still maintains the same O(1) space as seen in the brute-force approach. We just need to make some modifications to the code.

Explanation/Thought Process

• assign the length of the array to a variable and another (we'll call it idxOne) to represent the array index to be 1
• check if the array is empty, if it is, stop the operation
• if not, iterate through the array starting from the first index of the array
  • if idxOne - 1 is not equal to the current index of the array
    • write the said index to an array, where the array is idxOne
    • idxOne is incremented by one
• return idxOne

delDupsBetter.py

#!/usr/bin/env python3
def del_dups(arr):
    n = len(arr)
    idxOne = 1

    if not arr:
        return 0

    for i in range(1, n):
        if arr[idxOne - 1] != arr[i]:
            arr[idxOne] = arr[i]
            idxOne += 1
    return idxOne

test_delDupsBetter.py

#!/usr/bin/env python3
from delDupsBetter import del_dups

arr = [1, 2, 2, 3, 3, 3, 4, 5, 5]
dups = del_dups(arr)
print(dups)
print(arr[:dups])

result:

5
[1, 2, 3, 4, 5]

Problem With This Solution

None I could find. Plus, this is a bit cleaner than having to use nested loops.

LeetCode Solution

Unfortunately, not going to get creative with this one, reason being its unnecessary for this solution, so here it is:

leetcode_26.py

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        idxOne = 1
        for i in range(1, len(nums)):
            if nums[idxOne - 1] != nums[i]:
                nums[idxOne] = nums[i]
                idxOne += 1
        return idxOne

With that, I'll see you some time next week with more array-related questions, or maybe something new.
Remember to practice in your own free time though...