In this post, I want to talk about how to find a duplicate in a character array. Although the example is about an character array, this could easily be implemented to any type of value typed array in Java. Let's say that we are given an array of characters, and we want to know if this array has any duplicates in it. If the array contains a duplicate we will print that a duplicate was found, if no duplicate is present we will print that no duplicate was found. To tackle this problem, I would say our best course of action is to use a Set. If you are unfamiliar with what a set is, I would advise you to read this article.

The Java API has a Set class that we can use, specifically the HashSet. We will use this to store our data as we iterate through the array. There is a built in method called contains that will check if the character is currently in the set. If the condition is met, we have found our duplicate and will mark a boolean value so that we signal the correct print statement.

                                
import java.util.*;
class Main {
    public static void main(String[] args) {
        boolean hasDuplicate = false;
        char[] test_arr = {'a', 'c', 'c', 'f'};
        // initialize the HashSet
        Set<Character> char_set = new HashSet<>();
        for(int i = 0; i < test_arr.length; i++) {
            if(char_set.containse(test_arr[i])) {
                hasDuplicate = true;
                break;
            }
            char_set.add(test_arr[i]);
        }
        if(hasDuplicate == true)
            System.out.println("Array has a duplicate.");
        else
            System.out.println("Array has no duplicates");
    }
}
                                
                                Code copied
                            

The time complexity of the above code is at worst case O(n). This would be the case if the array had no duplicates, we would have to iterate through the entire array for this to be possible. The space complexity is O(n). This accounts for the HashSet that was initialized, and will be, in its worst case, the same size as the test array. The use of Java's data structures are a great tool for solving problems like this one.