3 ways to find Repeating number in given array in Java?

Problem: 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.

3 examples to find duplicate numbers in Java array

There are multiple ways to find repeating elements in array e.g. the brute force way, which requires each number to be compared with every other. You can also find duplicates by using 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). 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 is appeared 10 times in array then also only check will be required for it.

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 elements. 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 add() method takes O(1) time to add an element into HashSet.

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 later because it's 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 hashtable and print all elements whose count is more than 1.

The time complexity of this solution is O(n) + O(k)  =  O(n) because you need to iterate 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.

That's all about how to find repeating numbers in 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 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 time complexity of O(n) and space complexity of O(k)