Showing posts with label duplicate element. Show all posts
Showing posts with label duplicate element. Show all posts

Count Duplicate elements in an array

Given an array of intergers, and need to count the number of duplicate array elements. For example if the array contains {1,2,3,2,1,4} then {1,2} duplicate elements and output should be 2.
Only the constraints is to the solution should satisfy O(N) complexity. i.e, need to traverse the array only once and need to fine the duplicate elements.

Count Duplicate elements in an array



import java.util.HashMap;
import java.util.Map;

public class CountDuplicate {

 public static void main(String[] args) {
  
  int val[] = { 2, 4, 2, 5, 7, 3, 6, 8, 5, 2, 5, 8, 4, 1, 4, 6};
  
  int count = countDuplicateElements(val);
  
  System.out.println("No. of duplicate elements : "+count);
 }
 
 public static int countDuplicateElements(int[] val) {
  
  int count = 0;
  
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  for (int i=0;i<val.length;i++) {
   if(map.containsKey(val[i])) {
    if(map.get(val[i]) == 1) {
     count++;
    }
    map.put(val[i], map.get(val[i])+1);
   }else {
    map.put(val[i], 1);
   }
  }
  return count;
 }
}


OUPUT:

No. of duplicate elements : 5