Remove Duplicate Elements In Unsorted Array In Java

Identifying and removing duplicate elements from an unsorted array is a common programming challenge. This process is crucial in scenarios where only unique values are relevant, such as data processing, database operations, or optimizing memory usage. In this article, you will learn how to efficiently remove duplicate elements from an unsorted array in Java using various approaches.

Problem Statement

An unsorted array can contain multiple occurrences of the same element. The problem is to process this array and produce a new collection or array that contains each element only once, effectively removing all duplicates. The challenge lies in doing this efficiently, especially for large datasets, without relying on the array being pre-sorted.

For example, given an array like [1, 2, 3, 2, 1, 4], the desired output after removing duplicates would be [1, 2, 3, 4].

Example

Consider the following Java array with duplicate elements:

int[] originalArray = {5, 2, 8, 2, 5, 1, 9, 8};

Run

After applying a duplicate removal technique, the expected output should contain only unique elements, such as:

Unique Elements: [5, 2, 8, 1, 9]

Note that the order of unique elements might vary depending on the chosen approach.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of the following Java concepts is beneficial:

• Arrays: How to declare, initialize, and iterate over arrays.
• Collections Framework: Familiarity with interfaces like Set, List, and concrete classes like HashSet, LinkedHashSet, and ArrayList.
• Generics: Understanding how to use type parameters with collections.
• Big O Notation: Basic knowledge of time and space complexity helps in evaluating the efficiency of different algorithms.

Use Cases or Case Studies

Removing duplicate elements from an unsorted array is a fundamental operation with broad applications:

• Data Deduplication: In databases or data lakes, removing duplicate records before analysis saves storage and improves query performance.
• User Input Validation: Ensuring unique usernames, email addresses, or product IDs in web forms or applications.
• Search Engine Indexing: Storing unique keywords or URLs to build efficient search indexes.
• Resource Management: In network programming or operating systems, maintaining a list of unique active connections or processes.
• Recommendation Systems: Filtering out previously recommended or viewed items to present fresh content.

Solution Approaches

Here are several effective methods to remove duplicates from an unsorted array in Java, ranging from simple to more optimized.

Approach 1: Using HashSet

HashSet is part of Java's Collections Framework and implements the Set interface. Sets inherently store only unique elements. This makes HashSet an ideal choice for removing duplicates. When an element is added to a HashSet, it checks for its existence. If it's already present, the add operation is ignored.

• Summary: Convert the array to a HashSet to automatically filter out duplicates, then convert the HashSet back to an array or ArrayList.

// Remove Duplicates Using HashSet
import java.util.HashSet;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] originalArray = {5, 2, 8, 2, 5, 1, 9, 8};
        System.out.println("Original Array: " + Arrays.toString(originalArray));

        // Step 1: Create a HashSet to store unique elements
        HashSet<Integer> uniqueElements = new HashSet<>();

        // Step 2: Iterate through the original array and add elements to the HashSet
        // HashSet automatically handles uniqueness
        for (int element : originalArray) {
            uniqueElements.add(element);
        }

        // Step 3: Convert the HashSet back to an array (optional, can also use uniqueElements directly)
        // Note: The order of elements in the resulting array is not guaranteed to be the original order.
        int[] arrayWithoutDuplicates = new int[uniqueElements.size()];
        int i = 0;
        for (int element : uniqueElements) {
            arrayWithoutDuplicates[i++] = element;
        }

        System.out.println("Array after removing duplicates (HashSet): " + Arrays.toString(arrayWithoutDuplicates));
    }
}

Run

Sample Output:

Original Array: [5, 2, 8, 2, 5, 1, 9, 8]
Array after removing duplicates (HashSet): [1, 2, 5, 8, 9]

Stepwise Explanation:

1. An int array originalArray is initialized with duplicate values.
2. A HashSet called uniqueElements is created.
3. The code iterates through each element in the originalArray.
4. For each element, uniqueElements.add(element) is called. If the element is already present in the HashSet, add() returns false and doesn't add it again, ensuring uniqueness.
5. Finally, the elements from uniqueElements are copied into a new int array arrayWithoutDuplicates for demonstration, or the HashSet itself can be used if a Set collection is preferred. The order of elements in the output array is not necessarily the original insertion order, as HashSet does not guarantee order.
6. This approach has an average time complexity of O(N) because adding and checking for existence in a HashSet takes O(1) time on average.

Approach 2: Using LinkedHashSet

While HashSet is efficient, it does not preserve the order of elements. If maintaining the original insertion order of unique elements is important, LinkedHashSet is the perfect choice. LinkedHashSet extends HashSet but also maintains a doubly-linked list running through its entries, ensuring insertion order.

• Summary: Convert the array to a LinkedHashSet to remove duplicates while preserving the order of the first occurrence of each element, then convert back to an array or ArrayList.

// Remove Duplicates Using LinkedHashSet
import java.util.LinkedHashSet;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] originalArray = {5, 2, 8, 2, 5, 1, 9, 8};
        System.out.println("Original Array: " + Arrays.toString(originalArray));

        // Step 1: Create a LinkedHashSet to store unique elements and preserve order
        LinkedHashSet<Integer> uniqueElementsOrdered = new LinkedHashSet<>();

        // Step 2: Iterate through the original array and add elements to the LinkedHashSet
        // LinkedHashSet automatically handles uniqueness and maintains insertion order
        for (int element : originalArray) {
            uniqueElementsOrdered.add(element);
        }

        // Step 3: Convert the LinkedHashSet back to an array
        int[] arrayWithoutDuplicatesOrdered = new int[uniqueElementsOrdered.size()];
        int i = 0;
        for (int element : uniqueElementsOrdered) {
            arrayWithoutDuplicatesOrdered[i++] = element;
        }

        System.out.println("Array after removing duplicates (LinkedHashSet): " + Arrays.toString(arrayWithoutDuplicatesOrdered));
    }
}

Run

Sample Output:

Original Array: [5, 2, 8, 2, 5, 1, 9, 8]
Array after removing duplicates (LinkedHashSet): [5, 2, 8, 1, 9]

Stepwise Explanation:

1. Similar to the HashSet approach, an originalArray is defined.
2. A LinkedHashSet called uniqueElementsOrdered is created.
3. Elements from originalArray are added to uniqueElementsOrdered. LinkedHashSet ensures that only unique elements are stored, and their order in the set reflects their first appearance in the originalArray.
4. The elements are then transferred to a new int array arrayWithoutDuplicatesOrdered. This array now contains only unique elements, maintaining their original relative order.
5. This approach also has an average time complexity of O(N), but with a slightly higher constant factor due to the overhead of maintaining the linked list for order preservation.

Approach 3: Sorting the Array

Another common technique involves sorting the array first. Once sorted, duplicates will appear consecutively, making them easy to identify and remove. This method modifies the original array (or a copy) and changes the relative order of unique elements.

• Summary: Sort the array, then iterate through the sorted array, copying only unique elements to a new array.

// Remove Duplicates by Sorting
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] originalArray = {5, 2, 8, 2, 5, 1, 9, 8};
        System.out.println("Original Array: " + Arrays.toString(originalArray));

        // Step 1: Sort the original array
        // This brings duplicate elements together
        Arrays.sort(originalArray);
        System.out.println("Sorted Array: " + Arrays.toString(originalArray));

        // Step 2: Create a temporary array to store unique elements
        // The maximum size for this temporary array is the original array's length
        int[] tempArray = new int[originalArray.length];
        int uniqueCount = 0; // Tracks the number of unique elements

        // Step 3: Iterate through the sorted array
        if (originalArray.length > 0) {
            tempArray[uniqueCount++] = originalArray[0]; // Add the first element, which is always unique in its context
            for (int i = 1; i < originalArray.length; i++) {
                // If the current element is different from the last unique element added, it's a new unique element
                if (originalArray[i] != tempArray[uniqueCount - 1]) {
                    tempArray[uniqueCount++] = originalArray[i];
                }
            }
        }

        // Step 4: Create the final array with the correct size
        int[] arrayWithoutDuplicatesSorted = Arrays.copyOf(tempArray, uniqueCount);

        System.out.println("Array after removing duplicates (Sorted): " + Arrays.toString(arrayWithoutDuplicatesSorted));
    }
}

Run

Sample Output:

Original Array: [5, 2, 8, 2, 5, 1, 9, 8]
Sorted Array: [1, 2, 2, 5, 5, 8, 8, 9]
Array after removing duplicates (Sorted): [1, 2, 5, 8, 9]

Stepwise Explanation:

1. An originalArray is initialized.
2. Arrays.sort(originalArray) is used to sort the array in ascending order. This places identical elements next to each other.
3. A tempArray is created to store unique elements, and uniqueCount tracks its size.
4. The first element of the sorted array is always unique relative to what comes *before* it (as nothing comes before it), so it's added to tempArray.
5. The code then iterates from the second element. It compares the current element (originalArray[i]) with the last unique element added to tempArray (tempArray[uniqueCount - 1]).
6. If they are different, it means a new unique element has been found, which is then added to tempArray, and uniqueCount is incremented.
7. Finally, Arrays.copyOf() is used to create arrayWithoutDuplicatesSorted with the precise size (uniqueCount), containing only the unique elements in sorted order.
8. The time complexity for this approach is dominated by the sorting step, which is O(N log N) for typical efficient sorting algorithms like Merge Sort or Quick Sort used by Arrays.sort(). The subsequent iteration is O(N).

Conclusion

Removing duplicate elements from an unsorted array in Java can be achieved through various methods, each with its own advantages regarding efficiency and order preservation. HashSet provides the most efficient average-case time complexity (O(N)) if element order is not a concern. LinkedHashSet offers the same average-case efficiency while guaranteeing the preservation of insertion order. For situations where sorting is acceptable or even desirable, sorting the array first and then iterating (O(N log N)) is a robust, in-place (if modified carefully) solution.

Summary

• HashSet:
• Pros: Fastest for removing duplicates (average O(N) time complexity).
• Cons: Does not preserve the original order of elements.
• LinkedHashSet:
• Pros: Efficient (average O(N) time complexity) and preserves the original insertion order of unique elements.
• Cons: Slightly higher memory footprint than HashSet due to linked list maintenance.
• Sorting the Array:
• Pros: A clear, two-step process; useful if a sorted output is also desired.
• Cons: Changes the relative order of elements; higher time complexity (O(N log N)) than Set-based approaches.
• Choosing the right approach: Depends on whether maintaining element order is critical and the performance requirements for large datasets. For most general cases, LinkedHashSet offers a good balance of performance and order preservation.