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.
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)
The test case 1, checks if the input array has any element or not. It returns the length of the array.
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’.
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/