3 ways to find a duplicate 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 an array e.g. 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)

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 the array then also only a 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 the 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 the latter 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 the 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 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.

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)

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java: An Interview Refresher
Cracking the Coding Interview - 189 Questions and Solutions

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 Easy to Advanced Data Structures course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.