How to Check or Detect Duplicate Elements in Array in Java? Example Tutorial (original) (raw)

Detecting duplicate elements in Java array is another programming interview question I like. There could be a lot of ways you can check if your array contains duplicate elements or not and sometimes you discover a unique way of checking duplicates by asking this question on Java interview. The beauty of this question is that it has an endless number of follow-up question so if interviewee gets through this question you can ask to him about time complexity and space or to improve his algorithm to make it fast .you can even ask to find those duplicate elements in Array which even can go from one duplicate to many repeating elements in Array. As I said you can really test programming skills around an array of a Java programmer.

Checking Array for duplicate elements Java

In this Java tutorial, we will see a couple of ways to find if an array contains duplicates or not in Java. We will use the unique property of the Java collection class Set which doesn’t allow duplicates to check the java array for duplicate elements. Here are five ways we can check if an array has duplicates or not:

1. Brute Force Algorithm

The brute force method compares each element of Array to all other elements and returns true if it finds duplicates. Though this is not an efficient choice it is the one that first comes to mind.

2. Using Set Data Structure

Another quick way of checking if a Java array contains duplicates or not is to convert that array into Set. Since Set doesn’t allow duplicates size of the corresponding Set will be smaller than the original Array if Array contains duplicates otherwise the size of both Array and Set will be the same.

3. Using HashSet in Java

One more way to detect duplication in the java array is adding every element of the array into HashSet which is a Set implementation. Since the add(Object obj) method of Set returns false if Set already contains an element to be added, it can be used to find out if the array contains duplicates in Java or not.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join this Data Structures and Algorithms: Deep Dive Using Java course to fill the gaps in your understanding.

This diagram illustrates three methods for detecting duplicate elements in Java arrays:

Brute Force Method (Red):

• Uses nested loops to compare each element with others
• Time complexity: O(n²)
• Space complexity: O(1)
• Simple implementation with for-loops

HashSet Method (Blue):

• Uses a HashSet to track seen elements
• Time complexity: O(n)
• Space complexity: O(n)
• Efficient for large arrays

Collections Utility Method (Green):

• Uses Java Collections framework
• Time complexity: O(n)
• Can use Collections.frequency() or Stream API
• More concise code

In the next section, we will complete a code example of all three ways of duplicate detection on Array in java. Remember this discussion is just confirming whether an array contains duplicate or not , it's not finding out actual duplicate elements from Array though you can easily extend example Java program to accomplish that task based on your requirement.

This is also one of the popular programming interviews questions, asked in several interviews. I also suggest you solve problems from Crack the Coding Interview Questions book, one of the best resources to prepare for software developer interviews.

Code Example of checking duplicate on Array in Java

Here is a complete code sample of all the above methods to check if your array contains duplicates or not.

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class CheckDuplicatesInJavaArray {

public static void main(String args[]) {

String[] withDuplicates = new String[] {"one","two","three","one"};

String[] withoutDuplicates = new String[] {"one","two","three"};

System.out.println("Checking array with duplicate using brute force: " + bruteforce(withDuplicates));

System.out.println("Checking array without any duplicate using brute force: " + bruteforce(withoutDuplicates));

System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingSet(withDuplicates));

System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingSet(withoutDuplicates));

System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingAdd(withDuplicates));

System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingAdd(withoutDuplicates));

}

/*

* brute force way of checking if array contains duplicates in Java

* comparing each element to all other elements of array

* complexity on order of O(n^2) not advised in production

*/

public static boolean bruteforce(String[] input) {

for (int i = 0; i < input.length; i++) {

for (int j = 0; j < input.length; j++) {

if (input[i].equals(input[j]) && i != j) {

return true;

}

}

}

return false;

}

/*

* detect duplicate in array by comparing size of List and Set

* since Set doesn't contain duplicate, size must be less for an array which contains duplicates

*/

public static boolean checkDuplicateUsingSet(String[] input){

List inputList = Arrays.asList(input);

Set inputSet = new

HashSet(inputList)

;

if(inputSet.size()< inputList.size())

return true;

}

return false;

}

/*

* Since Set doesn't allow duplicates add() return false

* if we try to add duplicates into Set and this property

* can be used to check if the array contains duplicates in Java

*/

public static boolean checkDuplicateUsingAdd(String[] input) {

Set tempSet = new HashSet();

for (String str : input) {

if (!tempSet.add(str)) {

return true;

}

}

return false;

}

}

Output:

Checking array with duplicate using brute force: true

Checking array without any duplicate using brute force: false

Checking array with duplicate using Set and List: true

Checking array without any duplicate using Set and List: false

Checking array with duplicate using Set and List: true

Checking array without any duplicate using Set and List: false

That’s all on how to check if an Array contains duplicate or not in Java. You see we have used Java Collection API in two of our examples, there can be other pure programming solutions as well. You may be asked to detect duplicates without using Java API in the real interview.

Let us know if you come across some other good way of checking duplicates in an array without using Java API.

Other Java Tutorials you may find useful