How to Remove Duplicates from Array?

Let's dive in!

Duplicates in arrays can cause confusion and inaccuracies in your data so it’s important to remove them. But how?     Lets explore different methods to remove duplicates from an array —>>

Given an array of integers, the task is to remove duplicates from the array. For example, if given input  is arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}, then resulting array after reomoving duplicates should be arr[] = {1, 2, 3, 4, 5}.

Problem Statement

Intuition: Sorting will group duplicate elements together making it easier to identify and remove them.   Input array: 1 2 3 2 2 3 4 Sorted array: 1 2 2 2 3 3 4  Now, it's easy to spot and remove the duplicates.

Approach – 1  (Using Sorting)

Solution 1 - Using extra space   1. Sort the given array.  2. Use an auxiliary array to store unique elements and maintain their count.  3. Copy the unique elements back to the original array.

Solution 2 - Without using extra space   1. Sort the given array.  2. Use an in-place swapping approach. 3. Use an integer variable to keep track of unique elements & their position in the same array.

Time complexity: O(NlogN) because we have used sorting. Space complexity: O(N) using an extra array.

Here, we'll HashMap lookup to check for duplicate elements while traversing. Traverse the array & store elements in a HashMap. While traversing, place unique elements by checking if they are already present in HashMap.

Approach – 2  (Using HashMaps)

Time complexity: O(N) because of the use of hashmaps. Space complexity: O(N) using a hashmap.

Want to explore these approaches and learn how to implement them in various programming languages?

Click on the link below to start your journey.