Check whether array contain a duplicate value or not

In this post, I am going to explain different ways to check whether array contain duplicate values or not.

package com.sample.app.arrays;

public class DuplicateElementCheck {

	// private static <T> boolean containDuplicates(T[] data) { }

	public static void main(String[] args) {

		Integer[] elementsSet1 = new Integer[] { 2, 3, 5, 7, 11 };
		Integer[] elementsSet2 = new Integer[] { 2, 3, 5, 7, 11, 3 };

		System.out.println("Is elementsSet1 contain duplicates : " + containDuplicates(elementsSet1));
		System.out.println("Is elementsSet1 contain duplicates : " + containDuplicates(elementsSet2));

	}

}

All the approaches tested against above samples. I am going to implement the method ‘containDuplicates’ in different ways.

 

Approach 1: Using two for loops. This algorithm perform duplicate element check in 0(n^2) time.

private static <T> boolean containDuplicates(final T[] data) {

	if (data == null || data.length == 0) {
		throw new IllegalArgumentException("input must not be empty or null");
	}

	for (int i = 0; i < data.length; i++) {
		for (int j = i + 1; j < data.length; j++) {

			// Fast to check null references or both reference point to same object.
			if (data[i] == data[j]) {
				return true;
			}

			if (data[i].equals(data[j])) {
				return true;
			}
		}
	}
	return false;

}

Approach 2: Using a Set. Following snippet execute in O(n) time, but it takes additional space.

private static <T> boolean containDuplicates(final T[] data) {

	if (data == null || data.length == 0) {
		throw new IllegalArgumentException("input must not be empty or null");
	}

	final Set<T> tempSet = new HashSet<>(Arrays.asList(data));

	return tempSet.size() != data.length;

}

Approach 3: Using streams distinct and count methods.

private static <T> boolean containDuplicates(final T[] data) {

	if (data == null || data.length == 0) {
		throw new IllegalArgumentException("input must not be empty or null");
	}

	return Arrays.stream(data).distinct().count() != data.length;

}

  Approach 4: Sort the array and check the neighbour elements. Since sorting n element take O(n long n), the time complexity here is O(n log n).

 

private static <T extends Comparable<T>> boolean containDuplicates(final T[] data) {

	if (data == null || data.length == 0) {
		throw new IllegalArgumentException("input must not be empty or null");
	}

	Arrays.sort(data);

	for (int i = 0; i < data.length - 1; i++) {
		if (data[i].equals(data[i + 1])) {
			return true;
		}
	}

	return false;
}

 

 

 

You may like

Design Patterns

Interview Questions

Programming Questions

Java program to find a cycle in undirected graph

Check whether number is even or odd using bitwise operator

Merge sort iterative implementation