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
Fig 1: First iteration of array
2.) Second Iteration of array:
index = 1
Math.abs(arr[1]) = 1
arr[1] = 1, Set its value to -1
Fig 2: Second iteration of array
3.) Third Iteration of array:
index = 2
Math.abs(arr[2]) = 5
arr[5] = 3, Set its value to -3
Fig 3: Third iteration of array
4.) Similarly, In Fourth iteration will result in Fig 4.
Fig 4: Fourth iteration of array
5.) Fifth Iteration of array:
index = 4
Math.abs(arr[4]) = 2
arr[2] = -5 , Its value is negative, so 2 is duplicate value.
Fig 5: Fifth iteration of array
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
