Remove duplicates from the sorted arrays in Python

In this blog post, one can learn how they can remove duplicates from the sorted arrays in Python Programming Language. By duplicates, we mean the reputation of the elements in the array. We want an array that which all characters are unique. 

Remove duplicates from the sorted arrays in Python

To understand this problem let’s consider an array as an example. 

arr = {1,1,2,2,2,2,3,4,5,6,6,7}

After removing all the repeated elements the output should be:

arr = {1,2,3,4,5,6,7}

As one can see the array is already sorted in this case as we are working on sorted arrays only. There are two ways to do the same thing:

The first one is by using extra space in the form of a list while solving this problem. The code for the same is:

# This function returns the updated array's size.
def removeDuplicates(arr, n):
 
    # If the array is empty or has just one element, return it.
    if n == 0 or n == 1:
        return n
 
    temp = list(range(n))
 
    # Start traversing elements
    j = 0;
    for i in range(0, n-1):
 
        # Store the current element if it differs from the subsequent element.
        if arr[i] != arr[i+1]:
            temp[j] = arr[i]
            j += 1
 
    # If the last element is unique or repeated, store it as if it hasn't been stored before.
    temp[j] = arr[n-1]
    j += 1
     
    # Modify original array
    for i in range(0, j):
        arr[i] = temp[i]
 
    return j
 
# Driver code
arr = [1,1,2,2,2,2,3,4,5,6,6,7]
n = len(arr)
 
# removeDuplicates() returns new size of array.
n = removeDuplicates(arr, n)
 
# Print updated array
for i in range(n):
    print ("%d"%(arr[i]), end = " ")

Output:

The time and space complexity of this program is O(n). Now let’s move to the second method in which there is no allocation of the extra space to solve the above problem. In this approach, we will delete the repeating elements as we iterate through the list. The time complexity, in this case, is O(n) while the space complexity is only O(1) which means the constant amount of space is in use. 

Also Read: AlphaStar: Strategy game StarCraft II expertise