Remove Duplicates from Sorted Array
FREE BOOK > Problems for the day before your Coding Interview (on Amazon)
Price is set to 0. Click on Buy Now and it will be downloaded in your account.In this article, we have presented 3 different approaches to Remove Duplicates from Sorted Array. We can do this inplace using Two Pointer technique.
Table of contents:
 Problem statement
 Approach 1: Using extra space
 Approach 2: Using extra space modified
 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".