jayeshcp
1/8/2015 - 7:21 PM

## Find duplicate elements in array in O(N) time

Find duplicate elements in array in O(N) time

/*  Find if given array has duplicate elements (more than 1 occurence)
Time Constraint: O(N)
Author: Jayesh CP
*/

import java.util.*;
import java.lang.*;
import java.io.*;

public class FindDuplicates
{
public static void main (String[] args) throws java.lang.Exception
{

int[] nums = {1,2,3,4,5,5,6,7,8,8,9,1};

if(hasDuplicates(nums)) {
System.out.println("Found duplicates !");
} else {
System.out.println("No duplicates");
}

}

private static void hasDuplicates(int[] nums) {

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
boolean duplicate = false;

for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])) {
map.put(nums[i], (map.get(nums[i]) + 1));
duplicate = true;
break;
} else {
map.put(nums[i], 1);
}
}
// printDuplicates(map);
return duplicate;

}

/*
private static void printDuplicates(Map<Integer, Integer> map) {

Iterator it = map.entrySet().iterator();
while(it.hasNext()) {

Map.Entry pairs = (Map.Entry)it.next();
if((int)pairs.getValue() > 1) {
System.out.print(pairs.getKey() + " ");
}

}

}
*/
}