CODEWITHSUNDEEP
javaalgorithmperformancesortingcompare-and-swap
CoderSam
CoderSam

Reputation: 551

How to find the duplicates in an array in O(1) time in Java?

I am given a task to find the duplicates in an int array in O(1) time. My approach is to first sort the array and then find the duplicates using a linear search. I first used to sort the array by the swapping the numbers like this:

for(int i = 0;i<ar.length;i++) {
    for (int j = i + 1; j < ar.length; j++) {
        if (ar[i] > ar[j]) {
            buk = ar[i];
            ar[i] = ar[j];
            ar[j] = buk;
        }
    }
}

but the efficiency of this algorithm is O(i*j) which is not required for the solution. I have tried to use recurssion for sorting the array: 

static int x = 0;
static int[] swap(int[] arr) {
    if (x >= arr.length)
        return arr;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) {
            int bucket = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = bucket;
        }
    }
    x++;
    arr = swap(arr);
    return arr;
}

But this doesn't seem to be working at the moment. Please provide suggestions/alternate methods to sort an array, I have encountered this problem many times.

The Question is: find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.

Upvotes: 0

Views: 1508

Answers (1)

Stephen C
Stephen C

Reputation: 718788

It is mathematically impossible to find duplicates in O(1). You have to examine all N elements of the array at least once to test if each one is a duplicate. That is at least N operations, so the lower bound on the complexity is O(N).

Hint: you can do it in O(N) if you use (say) a HashSet to record each value that you have already seen. The snag is that a HashSet is a space-hungry data structure.

Please provide suggestions/alternate methods to sort an array, I have encountered this problem many times.

The simply way to sort an array of integers is to use Arrays::sort(int[]). That will be O(NlogN).

It is theoretically possible to sort an integer array in better than O(NlogN), but only if you can place a bound on the range of the integer. Lookup up counting sort. The complexity is O(max(N, R) where R is the difference between the smallest and largest numbers. The catch is that O(R) could be much larger than O(N) ... depending on the inputs.

But if you know that M is likely to be less than NlogN, you can use a variant of count sorting and use only O(M) bits of extra space to de-duplicate the array in O(max(M, N)). (I will leave you to figure out the details.)

Upvotes: 4

Related Questions