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