# Remove Duplicates from Sorted Array

## Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return array.

### Example

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

Input : [1,1,1]
Output: [1]

Input : [1,2]
Output: [1,2] ## Analysis


The problem can be solved easily by using an extra temp array and copy the unique elements to the temp array. Or with a little more work to do all work in place, if we have memory constraints.

Either case solution should run in O(n) speed.

Note Arrays are fixed length data structure, changing the length of an array in place is usually done by copying elements; We will use built in Array.Resize() apis to resize in place, and assume operation runs in O(1). But in reality this is not the case.

## Solution 1 - Using Temporary Array

This solution will create a temporary auxiliary array to store unique numbers.

The algorithm will traverse the original array, comparing each element with next, if not duplicate, it will copy the unique element to temporary.

C#

Time Complexity : O(n) Space Complexity : O(n)

## Solution 2 - Using Constant Space

This solution will utilize the same array to sort out the duplicates. It will only use an extra index to keep track of the last unique nubmer in the array.

The algorithm will traverse the array forward, comparing element with next element; if not equal elements it will copy the current element to last unique index location. Then array will be reseized at last unique index.

C#

Time Complexity : O(n) Space Complexity : O(1)

## Bouns

What if duplicates are allowed at most twice ?

### Example

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


The solution still straightforward, we will use a counter for duplicates and check for how many duplicates desired

C#

Time Complexity : O(n) Space Complexity : O(1)

Happy Coding!

Tags:

Updated: