Checking for Duplicacy in an array using Hashing Technique in Java

In this Java tutorial, we are going to check whether an array contains duplicate elements or not using hashing technique.

What is Hashing Technique and why we prefer Hashing here?

Hashing is a Technique to convert a range of key value into a range of indexes of an array. This problem can be solved simply using 2 for loops also but that increases the time complexity to O(n^2). Using Hashing Technique we can search for duplicacy in an array in one scan only. This algorithm takes O(n) time.

What Arrays.fill() do in Java?

java.util.Arrays.fill() method is in java.util.Array class. This method assigns a particular data type value to a specified range in the specified array.

  Syntax:

To fill all elements of an array to a specified value

Arrays.fill(array_name,value);

To fill a particular value in a specified range in array

                                 Arrays.fill(array_name, starting index , ending index,value);

Step by Step Approach:-

1. Input a value n from user specifying range of array.
2. Input an array a[] in the main function.
3. In result function take an array b[] , using Array.fill() make all elements of array b[] =0 initially.
4. Create a 1-D hash table and store the value in it on the basis of value of array a[] as index of b[].
5. Increment the value of b[index] from 1 to n, where index are the values of a[].
6. Finally, scan array b[] and check that if any element is greater than one, if yes the array a[] contains duplicate elements otherwise no.

Java Code to check for Duplicacy in array using Hashing Technique

import java.util.Scanner;
import java.util.Arrays;
import java.io.*;

 class Codespeedy
 {
     public static void result(int a[] , int n)
     {
           int b[]=new int[1000];
           
           int i;
           
           boolean flag=false;
           
           Arrays.fill(b,0);
           
           for(i=1;i<=n;i++)
              b[a[i]]++;
              
              for(i=1;i<=n;i++)
              {
                  if(b[i]>1)
                  {
                        flag=true;
                      System.out.println("Yes,array cointains duplicate elements");
                            break;
                  }
              }
              
              if(flag==false)
              System.out.println("No,array not cointains duplicate");
     }
       public static void main(String[] args)throws IOException
     {
         Scanner scan = new Scanner(System.in);
         
            
               int n=scan.nextInt();
               
               int a[]=new int[1000];
               
               for(int i=1;i<=n;i++)
               {
                   int x=scan.nextInt();
                     a[i]=x;
               }
               
              result(a,n);
     }
     
 }

INPUT  

4
1 2 3 2

OUTPUT

Yes,array cointains duplicate elements

One response to “Checking for Duplicacy in an array using Hashing Technique in Java”

1. Rajat says:

   January 11, 2019 at 9:54 am

   Helpful Technique

   Reply