Remove Duplicates from Sorted Array (With Solutions)

In order to succeed in the interview process for a product-based company such as Google, Amazon, or Microsoft, you must be familiar with the types of questions that will be asked in your technical interviews. As the competition for engineering talent grows more fierce every year, these companies are relying on their interview process to select candidates with an in-depth knowledge of computer science and engineering principles. To this end, they use a variety of tests to help them gain insight into your basic understanding of computer science, as well as your ability to solve complex problems. In this article, we will explore one such problem and provide solutions along with the corresponding code.

How to Remove Duplicates from a Sorted Array?

Given an integer array sorted in non-decreasing order, remove the duplicated such that the unique element appears only once.

For example :

Array = {2,3,4,4,5,6,6,6,8,8}

Output= 6

Solution Approaches to Remove Duplicates from Sorted Array

There are two methods to solve this problem. Let us understand both of them in detail below along with C++, Java and python codes:

Method 1: Brute force approach using extra memory

To detect and delete duplicates in a parallel manner, we could create a new array of the same size as the original array, and then compare each value with its neighbor. If there was a match, we would remove one instance of that value from the original array and add it to the auxiliary array.

We will also maintain a count of how many distinct values are in the original array at any given time, thereby allowing us to return the number of distinct values once our algorithm is complete. In the end, we will copy all values from our auxiliary array back into our original array and return it.

Algorithm

Create an auxiliary array of the same size as original
Compare each element of the original array with its neighbor element
If elements do not match
    Copy the unique element into an auxiliary array maintaining the count variable
Copy the elements of the auxiliary array back to the original array
Return the new size of the array

C++ Code

#include
using namespace std;
int RemoveDuplicates(int arr[], int a)
{
	if (a==0 || a==1)
		return a;

	int temp[a];

	int p = 0;
	for (int q=0; q<a-1; q++)

		if (arr[q] != arr[q+1])
			temp[p++] = arr[q];

	temp[p++] = arr[a-1];

	for (int q=0; q<p; q++)
		arr[q] = temp[q];

	return p;
}

int main()
{
	int arr[] = {2,3,4,4,5,6,6,6,7,8,8};
	int a = sizeof(arr) / sizeof(arr[0]);

	a = RemoveDuplicates(arr, a);

	cout << a;
}

Output

7

Java Code

class Main
{
	static int removeDuplicates(int arr[], int a)
	{
		if (a==0 || a==1)
			return a;
	
		int[] temp = new int[a];
		
		int q = 0;
		for (int p=0; p<a-1; p++)
			if (arr[p] != arr[p+1])
				temp[q++] = arr[p];
		
		temp[q++] = arr[a-1];
		
		for (int p=0; p<q; p++)
			arr[p] = temp[p];
	
		return q;
	}
	
	public static void main (String[] args)
	{
		int arr[] = {2,3,4,4,5,6,6,6,7,8,8};
		int a = arr.length;
		
		a = removeDuplicates(arr, a);
		System.out.print(a);
	}
}

Output

7

Python Code

def RemoveDuplicates(arr, a):

	if a == 0 or a == 1:
		return a

	temp = list(range(a))

	p = 0;
	for q in range(0, a-1):

		if arr[q] != arr[q+1]:
			temp[p] = arr[q]
			p += 1

	temp[p] = arr[a-1]
	p += 1
	
	for q in range(0, p):
		arr[q] = temp[q]

	return p

arr = [2,3,4,4,5,6,6,6,7,8,8]
a = len(arr)

a = RemoveDuplicates(arr, a)
print(a)

Output

7

Time Complexity

The time complexity of the above code is O(N) where N is the size of the array. Also, the space complexity of the solution is O(N) since we are creating an auxiliary array of the same size as the original array.

Method 2: Optimal approach using index pointer

This method follows the same approach as the above method. But the only difference is that we won’t be using the auxiliary array and instead do in-place swaps. Here, create the count variable to have the count of unique elements. This count variable will also help in maintaining the position of where to place the new element in the same array.

Algorithm

Create a counter variable to point to the index of unique elements.
Compare the element with its neighbor element
If elements do not match
    Consider the first element as unique and consider its pointer in the counter variable
    Keep comparing the other element with its neighbor element
As a result, the final array will consider only the unique element in the array

C++ Code

#include
using namespace std;

int RemoveDuplicates(int arr[], int a)
{
	if (a==0 || a==1)
		return a;

	
	int q = 0;
	for (int p=0; p < a-1; p++)
		if (arr[p] != arr[p+1])
			arr[q++] = arr[p];

	arr[q++] = arr[a-1];

	return q;
}

int main()
{
	int arr[] = {2,3,4,4,5,6,6,6,7,8,8};
	int a = sizeof(arr) / sizeof(arr[0]);

	a = RemoveDuplicates(arr, a);

	cout << a;
}

Output:

7

Java Code

class Main
{
	static int RemoveDuplicates(int arr[], int a)
	{
		if (a == 0 || a == 1)
			return a;
	
		int p = 0;
	
		for (int q = 0; q < a-1; q++)
			if (arr[q] != arr[q+1])
				arr[p++] = arr[q];
	
		arr[p++] = arr[a-1];
	
		return p;
	}
	
	public static void main (String[] args)
	{
		int arr[] = {2,3,4,4,5,6,6,6,7,8,8};
		int a = arr.length;
		
		a = RemoveDuplicates(arr, a);
		System.out.print(a);
	}
}

Output:

7

Python Code

def RemoveDuplicates(arr, a):
    if a == 0 or a == 1:
        return a
    arr.sort();
    p = 1
    for q in range(1, a):
        if arr[q] != arr[q-1]:
            arr[p] = arr[q]
            p += 1
    return p

arr = [2,3,4,4,5,6,6,6,7,8,8]
a = len(arr)

a = RemoveDuplicates(arr, a)
print(a)

Output:

7

Time Complexity

The time complexity of the above solution is O(N) where N is the number of elements in the array. It is because we traverse the entire array once to compare the elements and find the unique elements. Also, the space complexity of the above solution is O(1) as we do not require any extra space to remove the duplicated from the sorted array.

Conclusion

When it comes to interviews, especially technical ones, practice is the name of the game. Knowing how to answer interview questions is one thing; knowing how to answer them well is another. Preparation will help you come across as confident and knowledgeable when you're talking with a hiring manager, and in some cases, it can even make the difference between getting an offer or not. We recommend you learn and understand all these approaches for the problem "remove duplicates from sorted array" for getting an offer from your dream company and if you have any doubt, our coding help tutors are always ready to help you.