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 : 42. No duplicate element exists in an array |