[Solved] 2 Ways to Find Duplicate Elements in a given Array in Java - Example

Hello guys, today, you will learn how to solve another popular coding problem. You have given an array of objects, which could be an array of integers and or an array of Strings or any object which implements the Comparable interface. How would you find duplicate elements from an array? Can you solve this problem in O(n) complexity? This is actually one of the frequently asked coding questions from Java interviews. There are multiple ways to solve this problem, and you will learn two popular ways here, first the brute force way, which involves comparing each element with every other element, and other which uses a hash table-like data structure to reduce the time complexity of the problem from quadratic to linear, of course by trading off some space complexity.

This also shows how by using a suitable data structure, you can come up with a better algorithm to solve a problem. That's why a good knowledge of Data Structure and Algorithms are very important for all programmers.

If you are new to the programming world or want to refresh your knowledge about essential data structures like an array, string, linked list, hash table, binary tree, balanced tree, stack, queue, priority queue, etc then I suggest you go through a comprehensive data structure and algorithms course.

According to Data Structures and Algorithms: Deep Dive Using Java course  learning all essential data structures and algorithms like searching, sorting, and graph-based algorithms can make you better developer and also help in cracking coding interviews. 

How to find duplicates in a given array on O(n^2)

In the first solution, we compare each element of the array to every other element. If it matches then its duplicate and if it doesn't, then there are no duplicates. This is also known as a brute force algorithm to find duplicate objects from Java array.

The time complexity of this problem is O(n^2) or quadratic. When you give this solution to your interviewer, he will surely ask you to come up with O(n) time complexity algorithm, which we will see next.

Here is the code to find duplicate elements using a brute force algorithm in Java:
In this program, instead of printing the duplicate elements, we have stored them in a Set and returned from the method, but if the interviewer doesn't ask you to return duplicates, then you can simply print them into the console as I have done in next solution.

public static Set<Integer> findDuplicates(int[] input) {
        Set<Integer> duplicates = new HashSet<Integer>();

        for (int i = 0; i < input.length; i++) {
            for (int j = 1; j < input.length; j++) {
                if (input[i] == input[j] && i != j) {
                    // duplicate element found
                    duplicates.add(input[i]);
                    break;
                }
            }
        }

        return duplicates;
    }

If you are preparing for programming job interviews, then I also suggest you take a look at the Grokking the Coding Interview: Patterns for Coding Questions course on Educative, which contains many popular patterns for solving coding problems. This means you don't need to solve 100+ Leedcode problems but just need to learn a few patterns which are applicable to many programming problems.

How to Find duplicates in array in O(n) time Complexity

The second solution demonstrates how you can use a suitable data structure to come up with a better algorithm to solve the same problem. If you know, in Java, the Set interface doesn't allow duplicates, and it's based upon hash table data structure, so insertion takes O(1) time in the average case.

By using HashSet, a general-purpose Set implementation, we can find duplicates in O(n) time. All you need to do is iterate over an array using advanced for loop and insert every element into HashSet. Since it allows only unique elements, add() method will fail and return false when you try to add duplicates.

Bingo, you have to find the duplicate element, just print them off to console, as shown in the following program:

public static <T extends Comparable<T>> void getDuplicates(T[] array) {
        Set<T> dupes = new HashSet<T>();
        for (T i : array) {
            if (!dupes.add(i)) {
                System.out.println("Duplicate element in array is : " + i);
            }
        }

    }

This solution also demonstrates how you can use Generics to write type-safe code in Java. This method will work on any type of Java array, like Array with Integer, Array with String or any object which implements Comparable interface, but will not work with a primitive array because they are not objects in Java.

If you are preparing for programming job interviews, then I also suggest you take a look at the Cracking the Coding Interview book by Gayle McDowell, which contains 189 programming questions and solutions, good enough to do well on any programming job interviews like Java, C++, Python or Ruby.

Java Program to find duplicate elements in Java using Generics

Here is the Java program to combine both solutions, you can try running this solution on Eclipse IDE and see how it works. You can also write the JUnit test to see our solution work in all cases, especially corner cases like an empty array, array with null, etc.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import static java.lang.System.*;

/**
 * Java Program to find duplicate elements in an array. In this program, you
 * will learn two solution to find duplicate elements in integer array e.g.
 * brute force, by using HashSet data structure.
 * 
 * @author java67
 */

public class DuplicatesFromArray{

    public static void main(String args[]) {
        int[] withDuplicates = { 1, 2, 3, 1, 2, 3, 4, 5, 3, 6 };
        Set<Integer> duplicates = findDuplicates(withDuplicates);
        out.println("input array is : " + Arrays.toString(withDuplicates));
        out.println("Duplicate elements found in array are : " + duplicates);

        // now calling our generic method to find duplicates        
        String[] myArray = { "ab", "cd", "ab", "de", "cd" };
        out.println("input string array is : " + Arrays.toString(myArray));
        getDuplicates(myArray);
    }

    /**
     * Complexity of this solution is O(n^2)
     * 
     * @param input
     * @return
     */
    public static Set<Integer> findDuplicates(int[] input) {
        Set<Integer> duplicates = new HashSet<Integer>();

        for (int i = 0; i < input.length; i++) {
            for (int j = 1; j < input.length; j++) {
                if (input[i] == input[j] && i != j) {
                    // duplicate element found
                    duplicates.add(input[i]);
                    break;
                }
            }
        }

        return duplicates;
    }

    /**
     * Generic method to find duplicates in array. Complexity of this method is
     * O(n) because we are using HashSet data structure.
     * 
     * @param array
     * @return
     */
    public static <T extends Comparable<T>> void getDuplicates(T[] array) {
        Set<T> dupes = new HashSet<T>();
        for (T i : array) {
            if (!dupes.add(i)) {
                System.out.println("Duplicate element in array is : " + i);
            }
        }

    }

}

Output :
input array is : [1, 2, 3, 1, 2, 3, 4, 5, 3, 6]
Duplicate elements found in array are : [1, 2, 3]
input string array is : [ab, cd, ab, de, cd]
Duplicate element in array is : ab
Duplicate element in array is : cd

That's all about how to find duplicate elements in an array. You have now learned two ways to solve this problem in Java. The first solution is the brute force algorithm, which is demonstrated by finding duplicate elements on integer array, but you can use the logic to find a duplicate on any kind of array. The second solution uses the HashSet data structure to reduce the time complexity from O(n^2) to O(n), and it also shows you can write generic methods to find duplicates on any object array.

Other Coding Problems for Practice

• How to print the Pyramid pattern in Java? (solution)
• 10 Free Courses to learn Data Structure and Algorithms (courses)
• How to check if a given number is prime or not? (solution)
• How to solve the FizzBuzz problem in Java? (solution)
• 7 Best Courses to learn Data Structure and Algorithms (best courses)
• 100+ Data Structure and Algorithms Problems (solved)
• 10 Books to learn Data Structure and Algorithms (books)
• Write a program to print the highest frequency word from a text file? (solution)
• How to remove duplicate elements from ArrayList in Java? (solution)
• How to find if given String is a palindrome in Java? (solution)
• How to find a missing number in a sorted array? (solution)
• How to calculate factorial using recursion and iteration? (solution)
• How do you reverse word of a sentence in Java? (solution)
• How to find duplicate characters from String in Java? (solution)
• How to reverse an int variable in Java? (solution)
• How to check if a year is a leap year in Java? (answer)
• Write code to implement the Bubble sort algorithm in Java? (code)
• Top 10 Programming problems from Java Interviews? (article)
• Write code to implement the Quicksort algorithm in Java? (algorithm)
• How do you swap two integers without using a temporary variable? (solution)
• Write a program to check if a number is the power of two or not? (solution)
• How to reverse String in Java without using StringBuffer? (solution)
• Write a program to code insertion sort algorithm in Java (program)

Thanks for reading this article so far. If you like this array-based coding Interview question, then please share it with your friends and colleagues. If you have any doubts or feedback, then please drop a note. 

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structure in Java free course on Udemy. It's completely free, and all you need to do is create a free Udemy account to enroll in this course.