Remove Duplicates from Sorted Array

In this article, we have presented 3 different approaches to Remove Duplicates from Sorted Array. We can do this in-place using Two Pointer technique.

Table of contents:

  1. Problem statement
  2. Approach 1: Using extra space
  3. Approach 2: Using extra space modified
  4. Approach 3: Two pointer approach

Prerequisite: Two Pointer Technique

Let us get started with Remove Duplicates from Sorted Array. This is similar to Leetcode problem 26. Remove Duplicates from Sorted Array.

Problem statement

We have a sorted array with duplicates we need to return the length of the array without duplicates and modify the array by placing k unique elements in the first k slots of the array despite how the rest of the array will contain.

Example

Input: [1,1,2,3,3,4]
Output:

  • k = 4 (The length of unique elements)
  • array = [1,2,3,4,-,-]
    So, we need to modify it in place, but firstly we will see how to solve this problem with an extra space (not in place)

Approach 1: Using extra space

Aproach:

  • Create new temp array
  • Iterate through our input array.
  • Copy unique elements in temp, by checking whether it's exists or not in temp(will be easy in python) or by checking the next array element equal to the previous element in temp.
  • return temp, len(temp)

Solution

def remove_duplicates(nums):
    temp = []
    for num in nums:
        if num not in temp:
            temp.append(num)
    return len(temp)

input: [1,1,2,3,3,4]
output:
temp = [1,2,3,4], also k = len(temp) = 4
This is a simple solution but an extra space used and we want to optimize it.

Time complexity: O(n)

Space complexity: O(n)

What if we want to return the same array, here is a simple trick using also temp array.

Approach 2: Using extra space modified

  • Create new temp array
  • Iterate through our input array.
  • Copy unique elements in temp, by checking whether it's exists or not in temp(will be easy in python) or by checking the next array element equal to the previous element in temp.
  • Iterate again through the input array from i=0 till i=k where k is the len(temp) and the number of unique elements.
  • Replace each element in the array by the corresponding element in temp.
  • Delete temp.

Solution

def remove_duplicates(nums):
    temp = []
    for num in nums:
        if num not in temp:
            temp.append(num)
    n = len(temp)
    for i in range(len(temp)):
        nums[i] = temp[i]

    del temp[:]
    return len(nums[:n])

output: [1,2,3,4,3,4] where the first k slots(k=4) are our correct final result.
The above two solutions are good and a little pythonic but we want a more general solution without any extra space, this will lead us to the two pointer approach.

Approach 3: Two pointer approach

Aproach:

  • Declare two pointers i,k = 0,0

  • Assign nums[k] = nums[i] as the first element always unique

  • Iterate through the original array from the second element till the end of the array.

  • We keep moving i and fix k untill we find that nums[i] not equal to the nums[k] that mean new different/unique number appear then swap this new different/unique number with the number next to the previous unique element.
    ex: [0,0,0,1,...]
    k points to nums[0] = 0, i will continue moving from nums[1] untill 1 is found then nums[k+1] will be swapped with the 1, inorder to have two unique elements beside each others and so on...

  • return k+1

Solution

def remove_duplicates(nums):
    if len(nums)<1:
        return 0
    i,k = 0,0
    nums[k] = nums[i]
    for i in range(1,len(nums)):
        if nums[k]!=nums[i]:
            k+=1
            nums[k] = nums[i]
    return(k+1)

output:
k = 4 , nums = [1,2,3,4,3,4]

Time complexity: O(n)

Space complexity: O(1) no additional memory is required.

With this article at OpenGenus, you must have the complete idea of solving the problem of "Remove Duplicates from Sorted Array".