Arrays: Program to remove duplicate from a sorted array


Given a sorted array containing duplicate elements, we want to remove the duplicate elements from the sorted array

 
Approach
  1. The idea is to traverse the array and compare each element with the next one
  2. Since the array is sorted, all the duplicate elements will be next to each other
  3. We will create a new array called temp of same length as original array
  4. We will now traverse the given array and compare the element at ith position with element at i+1th position
    and see if they are not equal. When this is true, we store the element at ith position in the temp array.
    If the element at ith position is the same as element at i+1th position we do nothing and simply move to the next iteration
  5. Finally we copy back the elements of temp array into original array and display the elements
 
Complexity:

Time Complexity : O(n), where n is the number of elements in the array
Space Complexity: O(n), since we are using a temp array

 
Java Code
class RemoveDuplicates{

        public static int removeDuplicateElementsFromArray(int array[], int arrayLength){
           
            if(arrayLength == 0 || arrayLength == 1){
                return arrayLength;
            }
    
            int[] temp = new int[arrayLength];
            int j = 0;
            
            for(int i = 0; i < arrayLength-1; i++){
                if(array[i] != array[i+1]){
                    temp[j++] = array[i];
                }
            }
        
            temp[j++] = array[arrayLength-1];
            
            for (int i = 0; i < j; i++){
                array[i] = temp[i];
            }
    
            return j;
        }
    
        public static void main (String[] args) {
    
            int array[] = {10,10,20,20,20,30,30,40,40,40,50,50,50};
           
            int n = array.length;
            
            System.out.print("Input array: ");
            
            for(int i = 0; i < n; i++){
                System.out.print(array[i]+" ");
            }
           
            n = removeDuplicateElementsFromArray(array, n);
            System.out.println();
    
            System.out.print("Output array: ");
            
            for (int i = 0; i < n; i++)
               System.out.print(array[i]+" ");
        }
    
  }
 
Output

Input array: 10 10 20 20 20 30 30 40 40 40 50 50 50
Output array: 10 20 30 40 50



Thanks for feedback.



Read More....
Check if an array is a min heap
Convert a sorted array into a binary search tree - recursive approach
Print the elements of an array
Find the kth largest element in the array
Find the kth smallest element in the array
Merge two sorted arrays