3 ways to Find Duplicate Elements in a given Array in Java [Solved]

Hello guys, if you are wondering how to find duplicates from a given array in Java then you have come to the right place. This is one of the most popular coding problems from interviews and there are multiple ways to solve this problem. In this article, I will show you three ways to solve this problem. First, you will learn how to solve the problem using brute force way and then you will see how you can optimize and simplify the solution by using additional memory and using an appropriate data structure like a HashSet or Hash table. In the real interview, you may need to solve this problem in some constraints like you cannot use additional memory or additional data structure that's where knowing multiple ways to find duplicate in Java array really help.

Before we discuss a solution, let's get the problem statement right. You have given an int array that contains duplicate or repeating elements like numbers. You need to find all those repeating numbers from a given array. Remember, the array may contain 1, 2, or multiple duplicates. 

You need to print all of them. For example, if the given array is {1, 2, 3, 4, 5, 6, 1} then your program should print 1. Similarly, if the given array is {3, 3, 2, 2, 4} then your solution should return 2 and 3, the order is not important as long as you can identify all the repeating elements.

Btw, if you are preparing for coding interviews then I highly recommend you to join a data structure and algorithms course to revise essential concepts. 

If you need a recommendation then I suggest you check out Data Structures and Algorithms: Deep Dive Using Java course by Tim Buchalaka on Udemy. This course will teach you essential data structure concepts and algorithms in the Java programming language. 

3 Examples to Print Duplicates from Given Java array

As I said, there are multiple ways to find repeating elements in an array, like the brute force way, which requires each number to be compared with every other. You can also find duplicates by using the Set data structure which returns false if you try to add duplicates. 

If you need duplicate counts as well i.e. how many times a number has occurred then you can use a hashtable.

Once you build the table by looping over an array, you can print the repeated elements and their count by looping over hashtable. Any number which has appeared more than once is your duplicate.

1. Brute force way to find a repeating element in an array

One of the simplest solutions to this coding problem is to loop through the array and compare each number with every other. This will need two for loops, hence the complexity of this solution would be O(n^2). 

  /**
   * Brute force way to find duplicate in Java array
   * 
   * @param numbersWithDuplicates
   * @return duplicate number from given array
   */
  public static int duplicate(int[] numbersWithDuplicates) {
    for (int i = 0; i < numbersWithDuplicates.length; i++) {
      for (int j = i + 1; j < numbersWithDuplicates.length; j++) {
        if (numbersWithDuplicates[i] == numbersWithDuplicates[j]) {
          return numbersWithDuplicates[i];
        }
      }
    }
    throw new RuntimeException("No Duplicate Found");
  }

You can further improve it by keeping an identified repeating element in another array and checking if a number is already on that list.

So by using a space of O(k) where k is duplicate you can reduce the checking time considerably. For example, if a number has appeared 10 times in the array then also only a check will be required for it. This kind of trick really helps in coding interviews. 

Btw, if you are serious about your coding interview then I also suggest you master essential coding patterns like sliding window, fast and slow pointers, and merge intervals. You can use these patterns to solve many coding problems. 

If you need a resource, I highly recommend you to join Grokking the Coding Interview: Patterns for Coding Questions course from Educative, an interactive online coding platform. This course will teach you 15 such patterns which can be used to solve 100+ Leetcode problems. 

And, if you find Educative platform and their Grokking courses like Grokking the System Design Interview, Grokking the Object-Oriented Programming interview then consider getting Educative Subscription which provides access to their 250+ courses in just $14.9 per month. It's very cost-effective and great for preparing for coding interviews. 

2. Finding duplicates using HashSet

HashSet is an implementation of the Set interface in Java. By virtue of being Set, it doesn't allow duplicates. So if you try to add a number or object which is already present in HashSet, the add method will fail and return false.

This is your repeating element. This solution requires just one pass over an array which means O(n) time complexity and O(k) space complexity to store duplicates in HashSet. We are assuming that the add() method takes O(1) time to add an element into HashSet.

  /**
   * Return duplicate using HashSet
   * @param givenArray
   * @return duplicate number
   */
  public static int duplicateUsingHashSet(int[] givenArray) {
    Set<Integer> temporarySet = new HashSet<>();
    for (int number : givenArray) {
      if (!temporarySet.add(number)) {
        return number;
      }
    }
    throw new RuntimeException("No Duplicate Found");
  }

You can see that using a Data structure can make a lot of difference. It not only make your code cleaner but also improves the performance from quadratic to linear. 

3. Print repeated numbers and their count using Hashtable

You can also use a hash table data structure to find duplicates from an array in Java. JDK has a class called java.util.Hashtable, which is the sample implementation of a hash table data structure. You can use this class or HashMap to solve this problem.

The only difference between HashMap and Hashtable is that the former is faster than the latter because its methods are not synchronized. In this solution, you iterate over the array and store each element and their count in the hash table.

If an element doesn't exists in hashtable then store it with count 1 and if an element already exists then just increase its count by 1. Once you have built the hashtable, you can iterate over the hashtable and print all elements whose count is more than 1.

/**
   * Return duplicate using Hashtable
   * @param givenArray
   * @return
   */
  public static int duplicateUsingHashtable(int[] givenArray) {
    Map<Integer, Integer> numberWithCount = new Hashtable<>();
    for (int number : givenArray) {
      Integer count = numberWithCount.get(number);
      if( count == null){       
        numberWithCount.put(number, 1);
      }else{
        return number;
      }
    }
    throw new RuntimeException("No Duplicate Found");
  }

The time complexity of this solution is O(n) + O(k)  =  O(n) because you need to iterate the array one time, which is O(n), then you iterate over HashMap, which just contains duplicates, hence O(k). Assuming get() and put() method is giving O(1) performance. 

If you want to learn more about Big O notation and tips to improve the performance of algorithms, I suggest you join the Master the Coding Interview: Data Structures + Algorithms course by Andrei Negaoie on Udemy.

And, if you like Andrei's teaching style and his highly engaging course then you can also join his ZTM Academy where you can get access to all of his courses for one single price of $39 per month. 

Java Program to Find Duplicate Number in Given Array

Here is our complete Java program to find out the duplicate numbers in a given array in Java. This program encompasses all the three ways we have discussed so far.  You can copy-paste this program and run it in your favorite IDE.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Map;
import java.util.Set;

public class DuplicateInArraySolution {

  public static void main(String... legend) {
    int[] numbers = { 1, 2, 3, 4, 1, 5 };
    System.out.println("original array: " + Arrays.toString(numbers));
    System.out.println("Duplicate from array using brute force: "
        + duplicate(numbers));
    System.out.println("Duplicate from array using HashSet in Java: "
        + duplicateUsingHashSet(numbers));
    System.out.println("Duplicate from array using Hashtable in Java: "
        + duplicateUsingHashtable(numbers));
  }

  /**
   * Brute force way to find duplicate in Java array
   * 
   * @param numbersWithDuplicates
   * @return duplicate number from given array
   */
  public static int duplicate(int[] numbersWithDuplicates) {
    for (int i = 0; i < numbersWithDuplicates.length; i++) {
      for (int j = i + 1; j < numbersWithDuplicates.length; j++) {
        if (numbersWithDuplicates[i] == numbersWithDuplicates[j]) {
          return numbersWithDuplicates[i];
        }
      }
    }
    throw new RuntimeException("No Duplicate Found");
  }

  /**
   * Return duplicate using HashSet
   * @param givenArray
   * @return duplicate number
   */
  public static int duplicateUsingHashSet(int[] givenArray) {
    Set<Integer> temporarySet = new HashSet<>();
    for (int number : givenArray) {
      if (!temporarySet.add(number)) {
        return number;
      }
    }
    throw new RuntimeException("No Duplicate Found");
  }
  
  /**
   * Return duplicate using Hashtable
   * @param givenArray
   * @return
   */
  public static int duplicateUsingHashtable(int[] givenArray) {
    Map<Integer, Integer> numberWithCount = new Hashtable<>();
    for (int number : givenArray) {
      Integer count = numberWithCount.get(number);
      if( count == null){       
        numberWithCount.put(number, 1);
      }else{
        return number;
      }
    }
    throw new RuntimeException("No Duplicate Found");
  }
}

Output:

original array: [1, 2, 3, 4, 1, 5]
Duplicate from array using brute force: 1
Duplicate from array using HashSet in Java: 1
Duplicate from array using Hashtable in Java: 1

That's all about how to find repeating numbers in a Java array. You have learned three ways to solve this problem, the brute force ways, by using HashSet, and by using a hashtable. The first solution has the time complexity of O(n^2).

By using Set you reduce it to O(n) which is why people always say, choosing the right data structure can improve the solution. Btw, this needs a space tradeoff, we need O(k) more memory where k is a number of duplicates.

The third solution uses hashtable, which you need if you also want to print how many times a repeating element has appeared. This also has a time complexity of O(n) and space complexity of O(k)


Other array-based coding problems for Interviews:

• How to find all pairs in an array whose sum is equal to k (solution)
• How to remove duplicates from an array in Java? (solution)
• How to find the largest and smallest number in an array without sorting? (solution)
• How to find duplicates from an unsorted array in Java? (solution)
• How to find one missing number in a sorted array? (solution)
• How to find a missing value from an array containing 1 to 100? (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Recursive InOrder traversal Algorithm (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
• How to remove an element from an array in Java? (solution)
• How to check if an array contains a particular value? (solution)
• Iterative PreOrder traversal in a binary tree (solution)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this Java Array tutorial then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

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 Structures in Java for Beginners [FREE] course on Udemy. It's completely free and you just need an Udemy account to join this course.