# Finding duplicates in Array

Hi Friends,
I would like to know what should be the approach to solve questions like these:

1. In an array of X elements, check to see if there are any duplicate values by providing 2 approachs:

a. to maximize-performance (0(n))
b. to minimize-memory-usage

I wrote this test program to find duplicates and now I wonder how can i change my program to follow the above said 2 approaches:
``````import java.util.*;
public class test{
public static void main(String[] ar)
{
int[] arr = {3,5,6,4,2,3,5,2,4,2};
StringBuffer sb = new StringBuffer();

Arrays.sort(arr);
boolean flag=false;

for(int i=0;i<10;i++)
{
System.out.println(arr);
}

for(int i=0;i<9;i++)
{
if(arr[i]==arr[i+1]){
if(!flag)
sb.append(arr[i]+" ");
flag=true;
continue;
}else{
flag=false;
}
}
System.out.println("Duplicates:"+sb.toString());
}
}

• ###### 1. Re: Finding duplicates in Array
java80 wrote:
I wrote this test program to find duplicates and now I wonder how can i change my program to follow the above said 2 approaches:
You already have achieved b. The integers must be stored somewhere and you don't use any additional storage. The naive approach gives an O(N*N) algoritm but by first sorting you've changed that to an O(N*logN) algoritm which is better

To achieve a. you need to add a data structure namely a set. The algoritm goes,

For all integers in the array {
If the integer is in the set it's a duplicate.
Add the integer to the set.
}

For the set you can use a HashSet or implement your own set using an integer array. It's important that you can check whether an integer is in the set in O(1) time.

Thanks to the set's O(1) behavior the above algoritm will be O(N) and that's the fastest possible. The cost is the set you need.