Recent Posts

Remove Duplicates from Sorted Array

Written by

Anshuman Raina

Input: [1,1,1,1,1,2,2,3,3,3,3,4,4,4,5,6,6,6,7,7,7]

Output: [1,2,3,4,5,6,7]

 

The task at hand is clear, right? For any element in array present more than once, only a single entry should be added. Think of it as the UNIQUE operation in SQL, where we get only the unique values listed once in the array.

Firstly, we approach this problem by defining how we wish to store the resultant unique elements:

1. In a different array

2. In the same array.

Let us dive deep into the problem.

# Storing the elements in a different array

Before writing the code, we will write the pseudo-code for this problem. The steps for this part are :

  1. Initialize another array with same size say FINAL, and a variable which is currently at 0th index. This will be used to add values to FINAL array.
  2. Check which occurrence of the repeated element you wish to add in the array. Here we will show you the way to add the last occurrence. This is useful as this helps when adding the last element(details below).
  3. We check if the next element is equal to current one,
    • If Yes, skip
    • If no, add it to final array
  4. Add one repeated value in the FINAL array and increment variable.
  5. Remember to add the last number as well.

 

Now, this pseudocode differentiates from syntactical pseudo-code since this is a laymen representation of the thought process. So, writing this in code:

CODE :

void removeDuplicatesWithExtraSpace(int duplicatesArray[], int size){

if (size == 1 || size == 0){
	cout << "Sorry";
	return;
}

int final[size], j = 0;
for (int iterator = 0; iterator< size - 1; iterator++){
	if (duplicatesArray[iterator] != duplicatesArray[iterator + 1]){
		final[j] = duplicatesArray[iterator];
		j++;
	}
}

final[j] = duplicatesArray[size - 1];
for (int i = 0; i <= j; i++){
   cout << final[i] << endl;
}



}


int main(){


int dataDuplicates[] = { 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 7, 7 };
removeDuplicatesWithExtraSpace(dataDuplicates, 21);



}

The main drives the code, and is the same for both the approaches.

 

# Storing the elements in the same array

Before writing the code, we will write the pseudo-code for this problem. The steps for this part are :

  1. Instead of new array, here we will use the beginning of the same array to store the unique elements.
  2. Iterate and check if the next element is the same as current one.
    • If Yes skip current
    • If NO Add the element to beginning of array and increment the beginning variable.

The condition will stay the same here. Only the place where we add changes. We write this in code below:

Code :

#include <iostream>
using namespace std;

void removeDuplicatesWithoutExtraSpace(int duplicatesArray[], int size){


int j = 0;
if (size == 1 || size == 0){
	cout &lt;&lt; "Sorry";
	return;
}

for (int iterator = 0; iterator&lt; size - 1; iterator++){
	if (duplicatesArray[iterator] != duplicatesArray[iterator + 1]){
		duplicatesArray[j] = duplicatesArray[iterator];
		j++;
	}
}

duplicatesArray[j] = duplicatesArray[size - 1];
for (int i = 0; i &lt;= j; i++){
	cout &lt;&lt; duplicatesArray[i] &lt;&lt; endl;
}



}


int main(){
int dataDuplicates[] = { 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 7, 7 };
removeDuplicatesWithoutExtraSpace(dataDuplicates, 21);
}

 

For both cases, Output stays the same :

Output:

[1,2,3,4,5,6,7]

Other Approaches:

  1. Create a counter function to calculate a specific element’s count, and then jump forward by those steps in the sorted array
Remove Duplicates from Sorted Array