2 Ways to Remove Duplicates from Sorted Array - O(n) time

Given an input array of integers, your goal is to remove duplicates present from an sorted array in O(n) time by method 1: using extra space i.e., O(n) space and by method 2: using constant space i.e., O(1) space.

Method 1: Algorithm – Using Extra Space

Below is the algorithm to remove duplicates from sorted array using extra space (temp[] array)

1) create an array temp[] (extra space) to store unique elements.
2) Traverse through the array
   2.1) If the current element is not equal to next element then store that current element.
   2.2) Keep track of count of unique elements using variable 'j'.
3) Store the last element as it may be unique element or repeated and we have'nt stored previously.
4) Copy unique elements from temp[] array to inArray[]
5) Print the updated array inArray[]

Solution 1: RemoveDuplicatesSortedArrayExtraSpace.iava

package com.sneppets.dsalgo.examples;

/**
 * Program to remove duplicates from a sorted array in O(n) time and O(n) Space
 * @author sneppets.com
 */
public class RemoveDuplicatesSortedArrayExtraSpace {
	
	public static void main(String[] args)
	{
		int inArray[] = {1, 1, 2, 3, 3, 4, 5, 7};
		int arraySize = inArray.length;
		removeDuplicates(inArray, arraySize);				
	}

	private static void removeDuplicates(int[] inArray, int arraySize) {
		
		//create an array temp[] (auxillay space) to store unique elements
		int[] temp = new int[arraySize];
		
		//Traverse through the array
		int j=0;
		for (int i=0; i<arraySize-1; i++)
		{
			//if the current element is not equal to
			//next element then store that current element 
			if(inArray[i] != inArray[i+1])
			{
				temp[j++] = inArray[i];
			}
		}	
		//store the last element as it may be unique element
		//or repeated and we have'nt stored previously
		temp[j++] = inArray[arraySize-1];		
		
		//printUpdatedArray(temp, j);
		
		//Update the original array with removed duplicates
		for (int i=0; i<j; i++)
		{
			inArray[i] = temp[i];
		}
		//print the updated array
		printUpdatedArray(inArray, j);
	}

	private static void printUpdatedArray(int[] inArray, int arraySize) {
		
		for(int i=0; i<arraySize; i++)
		{
			System.out.print( inArray[i]+ " ");
		}
		
	}	

}

Output

1 2 3 4 5 7

Time Complexity – O(n) time (Single Traversal)

Space Complexity – O(n) space (Since an array temp[] extra space is created/utilized to store unique elements)

Method 2: Algorithm – Without Extra Space

Below is the algorithm to remove duplicates from sorted array without any extra space.

In this approach maintain the separate index for the same array i.e., inArray[] instead of creating temp[] array (different array) to store unique elements.

1) Maintain separate index for same array (inArray[]) 
2) Traverse through the array
   2.1) If the current element is not equal to next element then store that current element. 
   2.2) Maintain another updated index for same array i.e., 'j'.  
3) Store the last element as it may be unique element or repeated and we have'nt stored previously.
4) Print the updated array (inArray[])

Solution 2: RemoveDuplicatesSortedArrayContantSpace.java

package com.sneppets.dsalgo.examples;

/**
 * Program to remove duplicates from a sorted array in O(n) time using constant space i.e., O(1) space
 * @author sneppets.com
 */
public class RemoveDuplicatesSortedArrayConstantSpace {
	
	public static void main(String[] args)
	{
		int inArray[] = {1, 1, 2, 3, 3, 4, 5, 7};
		int arraySize = inArray.length;
		removeDuplicates(inArray, arraySize);				
	}

	private static void removeDuplicates(int[] inArray, int arraySize) {		
		
		//To maintain separate index for same array (inArray[])
		int j=0;
		
		//Traverse through the array
		for (int i=0; i<arraySize-1; i++)
		{
			//if the current element is not equal to
			//next element then store that current element 
			if(inArray[i] != inArray[i+1])
			{
				inArray[j++] = inArray[i];
			}
		}	
		//store the last element as it may be unique element
		//or repeated and we have'nt stored previously
		inArray[j++] = inArray[arraySize-1];		
		
		//print the updated array
		printUpdatedArray(inArray, j);
	}

	private static void printUpdatedArray(int[] inArray, int arraySize) {
		
		for(int i=0; i<arraySize; i++)
		{
			System.out.print( inArray[i]+ " ");
		}
		
	}	

}

Output

1 2 3 4 5 7

Time Complexity – O(n) (Single Traversal)

Space Complexity – O(1) (Since maintaining separate index for the same array i.e., inArray[] instead of creating temp[] array i.e., different array to store unique elements)

2 Ways to Remove Duplicates from Sorted Array – O(n) time

Method 1: Algorithm – Using Extra Space

Solution 1: RemoveDuplicatesSortedArrayExtraSpace.iava

Method 2: Algorithm – Without Extra Space

Solution 2: RemoveDuplicatesSortedArrayContantSpace.java

Recommended Posts

Reference