Remove Duplicates in Sorted Array

Have you ever wanted to know how the “Remove Duplicates” feature in excel works?

Here’s a little preview in code language just for you.

Given array with N=5

Now, let’s say we have the above array as input.

Given it is a sorted array, our task is to remove the duplicate elements from the array, namely the extra 2 and 5 and return the length of the “ no duplicates” Array.

The output would look something like (2,4,5) and the value returned would be 3, which is the length of the updated array.

Method 1: Using extra space

Time Complexity: O(n)

Space Complexity: O(n)

Test Case 1

The test case 1, checks if the input array has any element or not. It returns the length of the array.

Another array called temp is used

A new array temp is initialized and then after comparing the elements, the unique elements in A[n] are copied in temp[n]. The length of the temp array is being stored in j.

At the end, the temp array elements are copied directly in the original array.

Method 2: Constant Space O(1)

Time Complexity: O(N)

Space Complexity: O(1)

Here, we just maintain a separate index for same array as maintained for different array in Method 1 using ‘j’.

Method 2

The initial test case is the same to check if the array is null or not, but the for loop is executed without creating an extra array for storage.

So, there you have it folks, hope you like it. For the source of the code, you can refer to,

https://www.geeksforgeeks.org/remove-duplicates-sorted-array/