Check if array contains duplicate elements using java (example)

Problem Statement:

• Given an array of integer, we would like to find out, whether array contains any duplicate elements.
• The numbers in an array shall be in range from 0 to n-1
• All the elements in array shall be positive numbers

Solution: Check if array contains duplicate elements

• We will apply simple trick to check whether array contains duplicates.
• We will negate the value of element, when we first visit an element.

Algorithms – find duplicates in an array using java

1.) First Iteration of array:

• index = 0
• Math.abs(arr[0]) = 2
• arr[2] = 5, Set its value to -5

2.) Second Iteration of array:

• index = 1
• Math.abs(arr[1]) = 1
• arr[1] = 1, Set its value to -1

3.) Third Iteration of array:

• index = 2
• Math.abs(arr[2]) = 5
• arr[5] = 3, Set its value to -3

4.) Similarly, In Fourth iteration will result in Fig 4.

5.) Fifth Iteration of array: 

• index = 4
• Math.abs(arr[4]) = 2
• arr[2] = -5 , Its value is negative, so 2 is duplicate value.

Program – Check if array contains duplicate elements in java

package org.learn.arrays;

public class CheckDuplicates {

	public static void main(String[] args) {
		int[] array = { 2, 1, 5, 4, 2, 3, 1 };
		isDuplicate(array);

		array = new int[] { 2, 1, 3, 0 };
		isDuplicate(array);
	}

	private static void isDuplicate(int[] numbers) {
		
		for (int index = 0; index < numbers.length; index++) {
			int absIndex = Math.abs(numbers[index]);
			
			if (numbers[absIndex] < 0) {
				// We have already seen this number
				System.out.println("1. Duplicate number exist in array at index : " + index);
				return;

			} else { // We are seeing this number for first time
				numbers[absIndex] = -numbers[absIndex];
			}
		}
		System.out.println("2. No duplicate element exists in an array");
		return;
	}
}

Output – Check if array contains duplicate elements in java

1. Duplicate number exist in array at index : 4
2. No duplicate element exists in an array