find duplicates in integer array with boundaries.

Question

Below is the problem description and algorithm that I have written. Is there anything to be done to improve this algorithm?

Given an integer array of unknown size, containing only numbers between 0 and 30, write a function to return an integer array containing all of the duplicates.

int[] findDupes(int[] array) {
    int[] found = new int[30];
    int[] dupes = new int[30];
    int dupesCount = 0;
    for (int i = 0; i < array.length; i++) {
        if (found[array[i]] <= 1) {
            found[array[i]]++;              
        }else{
            continue;
        }
        if(found[array[i]] > 1){
            dupes[dupesCount++] = array[i];
            if (dupesCount == 30)
                break;
        }
    }
    if (dupesCount == 0)
        return new int[0];
    return dupes;
}

Am assuming that the best case for running this algorithm would n or 30 whichever is lower and the worst case for running this algorithm is n, since I have to scan the entire array to find duplicates. Any comments?

Answer 1

You've got the right idea, but ask yourself, what does this block do, exactly

    if(found[array[i]] > 1){
        dupes[dupesCount++] = array[i];
        if (dupesCount == 30)
            break;
    }

when does it fire?

Walk through your code with a couple of samples including an array of 1000 occurrences of 0.

What exactly are you returning? why do you need to special case 0.

Also the best case run time is going to be greater than 30. What is the minimum input that makes it stop before reaching the end?

Answer 2

Something strange:

    if (found[array[i]] <= 1)              
    }else{
        continue;//happens if found[array[i]] > 1
    }
    if(found[array[i]] > 1){//usually don't get here, because of continue

Is the continue a fix to only add a number once? Although it works, the code is misleading.

Do you have to return a 30 length array if there is only one duplicate?

I'd suggest making your code slower and better by splitting tasks.

Answer 3

here is the modified version with comments embedded.

int[] found = new int[3];
    int[] dupes = new int[3];
    int dupesCount = 0;
    for (int i = 0; i < array.length; i++) {
        if (found[array[i]] <= 1) {
            found[array[i]]++;              
        }
        if(found[array[i]] > 1){ //duplicate found
            dupes[dupesCount++] = array[i];

            // if 30 duplicate are found don't scan the array any more
            // since the distinct numbers are only 30
            if (dupesCount == 30) 
                break;
        }
    }
    if (dupesCount == 0)
        return null;
    return dupes;

Answer 4

Need more precise definition of the problem. Are there only 1 or 2 occurrences of an integer? Can there be 0 or 3 occurrences?

If there are only 1 or 2 occurrences of an integer, and integers range from 1 to 30; I would have a BitSet, and flip the bit as I find an integer. When I am done reading the original array, all the bits that are 0 will represent the integers containing duplicates.