Remove duplicates from sorted array

Table of Contents

Problem Statement

“Remove duplicates from sorted array” states that you are given a sorted array of size N. You need to remove the duplicate elements from the array. Print the array containing unique elements after the removal of duplicate elements.

Example

a [] = {1, 1, 1, 1}

{1}

Explanation: Since the input array contained only 1. The only distinct element is also only 1.

a [] = {1, 3, 3, 3, 4}

{1, 3, 4}

Explanation: The repeated 3 and 4 were removed, thus the resultant array has only {2, 3, 4}.

Approach

Here, we have taken an already sorted array as input. And now we need to remove duplicates. If the array was not sorted then it would have had numbers arranged in a random fashion. And then removal of duplicates would have been a time-consuming task. But since the numbers are already sorted in the array. So, we are sure that if the duplicates exist in the array they will be in a continuous fashion. That is we can pick a number and its duplicates and they will always exist as contiguous subarray. Using this fact we have two approaches, the first approach is a little bit space consuming but the second approach uses the initial array to reduce the space complexity. So, choosing any approach of the two depends on the task.

Iterative Method

Algorithm

1. Initialize an array of integer type of size n.
2. Check if n is equal to 0 or 1, return n.
3. Create another array of integer type of size n and an integer variable j as 0.
4. Traverse all the values of the original array one by one except the last element. If the value of the element at current index in array a[ ] is not equal to the value of the element at current index + 1 in array a[ ], store the element at current index in array a[ ] in new array at index j+1. 
5. Store the last element of the original array in the new array if it's unique.
6. Modify the original array by replacing its elements with the elements of new array.
7. Return the size of the new array.

Code to remove duplicates from a sorted array

C++ Program

#include<iostream> 
using namespace std; 
  
int deleteDuplicates(int a[], int n){ 
    if(n==0 || n==1) 
        return n; 
  
    int b[n], j = 0; 
    for (int i=0; i<n-1; i++) 
        // If current element is not equal 
        // to next element then store that 
        // in new array b[]
        if (a[i] != a[i+1]) 
            b[j++] = a[i]; 
  
    // Store the last element 
    b[j++] = a[n-1]; 
  
    // copy new array in original array 
    for (int i=0; i<j; i++) 
        a[i] = b[i]; 
  
    return j; 
} 
int main(){ 
    int a[] = {1, 2, 2, 3, 4, 4, 9}; 
    int n = sizeof(a) / sizeof(a[0]); 
    n = deleteDuplicates(a, n); 
    for (int i=0; i<n; i++) 
       cout<<a[i]<<" "; 
    return 0; 
}

1 2 3 4 9

Java Program

class delete{ 
    
    static int deleteDuplicates(int a[], int n){ 
        if(n==0 || n==1) 
            return n; 
       
        int[] b = new int[n]; 
          
        // Start traversing elements 
        int j = 0; 
        for (int i=0; i<n-1; i++) 
            // If current element is not equal 
            // to next element then store it 
            // in new array b[]
            if (a[i] != a[i+1]) 
                b[j++] = a[i]; 
          
        // Store the last element 
        b[j++] = a[n-1];    
          
        // copy new array in original array 
        for (int i=0; i<j; i++) 
            a[i] = b[i]; 
       
        return j; 
    } 
      
    public static void main (String[] args)  
    { 
        int a[]={1, 2, 2, 3, 4, 4, 9}; 
        int n = a.length; 
        n = deleteDuplicates(a, n); 
        for (int i=0; i<n; i++) 
           System.out.print(a[i]+" "); 
    } 
}

1 2 3 4 9

Complexity Analysis

Time Complexity

O(N), because we have once traversed the initial array.

Space Complexity

O(N) because in the worst case when all elements are distinct, we will have to store N elements.

Space Efficient Method