Efficient Duplicate Removal from Java Arrays

Efficiently removing duplicate elements from an array is a fundamental task in programming. This article explores three distinct Java approaches, each offering a different balance between speed and memory usage. Understanding these trade-offs is crucial for selecting the optimal method for your specific application.

Table of Contents

• Using a Temporary Array
• Using a Separate Index
• Using the Arrays.sort() Method
• Method Comparison

Using a Temporary Array

This straightforward method iterates through the input array. Each element is checked against a temporary array containing only unique elements encountered so far. If an element is not found in the temporary array, it’s added. While easy to understand, its nested loop structure leads to a time complexity of O(n²), making it inefficient for large arrays.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesTempArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0]; 
        }

        int[] uniqueArr = new int[arr.length]; 
        int uniqueCount = 0;

        for (int i = 0; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < uniqueCount; j++) {
                if (arr[i] == uniqueArr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount); 
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 5, 5, 5};
        int[] uniqueArr = removeDuplicatesTempArray(arr);
        System.out.println("Original array: " + Arrays.toString(arr));
        System.out.println("Array with duplicates removed: " + Arrays.toString(uniqueArr));
    }
}

Time Complexity: O(n²)
Space Complexity: O(n)

Using a Separate Index

This method improves space efficiency by modifying the original array in place. It uses a separate index to track the position of the next unique element. The array is iterated, and unique elements are moved to the positions indicated by this index. While space-efficient (O(1)), it still suffers from O(n²) time complexity due to the nested loops.

public class RemoveDuplicates {

    public static int[] removeDuplicatesIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int index = 1; 
        for (int i = 1; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < index; j++) {
                if (arr[i] == arr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                arr[index++] = arr[i];
            }
        }
        return Arrays.copyOf(arr, index);
    }
    //main method remains the same as above
}

Time Complexity: O(n²)
Space Complexity: O(1)

Using the Arrays.sort() Method

This approach leverages Java’s built-in sorting functionality. Sorting the array first brings duplicate elements together. A subsequent single pass through the sorted array identifies and retains only the first occurrence of each element. The time complexity is dominated by the sorting algorithm (O(n log n)), offering significantly better performance for larger datasets than the previous methods.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        Arrays.sort(arr); 
        int[] uniqueArr = new int[arr.length];
        uniqueArr[0] = arr[0]; 
        int uniqueCount = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount);
    }
    //main method remains the same as above
}

Time Complexity: O(n log n)
Space Complexity: O(n)

Method Comparison

The choice of method depends on the size of your data and your priorities. For smaller arrays, the simplicity of the temporary array method might suffice. For larger arrays, the performance gains of the Arrays.sort() method outweigh its slightly higher space complexity. The separate index method offers a space-efficient solution, but its quadratic time complexity makes it less attractive for large datasets.