# 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)

Subscribe
Notify of