Given a sorted array, the task is to remove the duplicate elements from the array.
Examples:
Input: arr[] = {2, 2, 2, 2, 2}
Output: arr[] = {2}
new size = 1
Input: arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
Output: arr[] = {1, 2, 3, 4, 5}
new size = 5
Method 1: (Using extra space)
- Create an auxiliary array temp[] to store unique elements.
- Traverse input array and one by one copy unique elements of arr[] to temp[]. Also keep track of count of unique elements. Let this count be j.
- Copy j elements from temp[] to arr[] and return j
C++
// Simple C++ program to remove duplicates #include <iostream> using namespace std;   // Function to remove duplicate // elements This function returns // new size of modified array. int removeDuplicates(int arr[], int n) {     // Return, if array is empty or     // contains a single element     if (n == 0 || n == 1)         return n;       int temp[n];       // Start traversing elements     int j = 0;       // If current element is not equal     // to next element then store that     // current element     for (int i = 0; i < n - 1; i++)         if (arr[i] != arr[i + 1])             temp[j++] = arr[i];       // Store the last element as whether     // it is unique or repeated, it hasn't     // stored previously     temp[j++] = arr[n - 1];       // Modify original array     for (int i = 0; i < j; i++)         arr[i] = temp[i];       return j; }   // Driver code int main() {     int arr[] = {1, 2, 2, 3, 4,                  4, 4, 5, 5};     int n = sizeof(arr) / sizeof(arr[0]);       // RemoveDuplicates() returns     // new size of array.     n = removeDuplicates(arr, n);       // Print updated array     for (int i = 0; i < n; i++)         cout << arr[i] << " ";       return 0; }   // This code is contributed by Aditya Kumar (adityakumar129) |
Output:Â Â
1 2 3 4 5
Time Complexity: O(n)Â
Auxiliary Space: O(n)
Method 2: (Constant extra space)Â
Just maintain a separate index for same array as maintained for different array in Method 1.
C++
// C++ program to remove // duplicates in-place #include<iostream> using namespace std;   // Function to remove duplicate // elements. This function returns // new size of modified array. int removeDuplicates(int arr[], int n) {     if (n==0 || n==1)         return n;       // To store index of next     // unique element     int j = 0;       // Doing same as done in Method 1     // Just maintaining another updated     // index i.e. j     for (int i = 0; i < n - 1; i++)         if (arr[i] != arr[i + 1])             arr[j++] = arr[i];       arr[j++] = arr[n - 1];       return j; }   // Driver code int main() {     int arr[] = {1, 2, 2, 3, 4,                  4, 4, 5, 5};     int n = sizeof(arr) / sizeof(arr[0]);       // removeDuplicates() returns new     // size of array.     n = removeDuplicates(arr, n);       // Print updated array     for (int i=0; i<n; i++)         cout << arr[i] << " ";       return 0; } |
Output:Â
1 2 3 4 5
Time Complexity : O(n)Â
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
