Find the first duplicate with the minimal next occurrence

Question

I am trying to solve a challenge, I wrote my solution and it passes all test cases except some hidden test cases. I can't think another case in which my method fails and don't know what to do anymore. Here it is:

int firstDuplicate(int[] a) {

int[]   indexCount;
int     duplicate, temp;
boolean check;

duplicate  = -1; temp = a.length;
indexCount = new int[a.length];
check      = false;

for( int i = 0; i < a.length; i++ ){

    if( indexCount[a[i]-1] == 0 ){
        indexCount[a[i]-1] = i+1;
        check = false;
    }else{
        indexCount[a[i]-1] = (i+1) - indexCount[a[i]-1];
        check = true;
    }
    if( check && indexCount[a[i]-1] < temp ){
        duplicate = a[i];
        temp      = indexCount[a[i]-1];
    }
}
return duplicate;

}

Instructions are:

Write a solution with O(n) time complexity and O(1) additional space complexity. Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index.

Example

For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

Answer 1

Here is what I have. Runs in O(n) and uses O(1) space. Correct me if I'm wrong here.

Since my input cannot have a value that's more than the length, I can use mod operator for indexing on the same array and add the length to the value in index. As soon as I encounter a value that larger than the length, that means I've already incremented that before, which gives me the duplicate value.

public int firstDuplicate(int[] arr) {
    int length = arr.length;

    for (int i = 0; i < length; i++) {
        int expectedIndex = arr[i] % length;
        if (arr[expectedIndex] > length) {
            return arr[i] > length ? arr[i] - length : arr[i];
        } else {
            arr[expectedIndex] += length;
        }
    }

    return -1;
}

Answer 2

This answer is based on @Mehmet-Y's answer and all credit goes to Mehmet-Y. This version addresses the three issues I pointed out in the comments. I will delete this answer if the original gets corrected.

The general approach is to use the original array for storage instead of allocating a new one. The fact that no value may be less than one or greater than the length suggests that you can use the array as a set of indices to flag an element as "already seen" by either negating it or adding/subtracting the array length to/from it.

To achieve O(n) time complexity, you have to solve the problem in a fixed number of passes (not necessarily one pass: the number just can't depend on the size of the array).

But how do you decide which duplicate has the smallest second index? I would suggest using two different flags to indicate an index that is already seen vs. the second item in a duplicate pair. For this example, we can set the index flag by incrementing the elements by the length, and marking duplicates by negating them. You will need a second pass to find the first negagive in the array. You can also use that pass to restore the elements to their original values without sacrificing O(n) time complexity.

Here is a sample implementation:

int firstDuplicate(int[] a)
{
    // assume all elements of a are in range [1, a.length]
    // An assertion of that would not increase the time complexity from O(n)
    int len = a.length;
    for(int i = 0; i < len; i++) {
        // a[i] may be > len, but not negative.
        // Index of bin to check if this element is already seen.
        flagIndex = (a[i] - 1) % len;
        if(a[flagIndex] > len) {
            // If already seen, current element is the second of the pair.
            // It doesn't matter if we flag the third duplicate,
            // just as long as we don't tag the first be accident.
            a[i] = -a[i];
        } else {
            // Flag the element as "already seen".
            // This can be done outside the else, but you might run
            // into (more) overflow problems with large arrays.
            a[flagIndex] += len;
        }
    }
    // Search and stash index of first negative number
    for(int i = 0; i < len; i++) {
        if(a[i] < 0) {
            return -a[i] % len;
        }
    }
    // Nothing found, oh well
    return -1;
}

If you want to take advantage of the second pass to restore the original values of the array, replace

for(int i = 0; i < len; i++) {
    if(a[i] < 0) {
        return -a[i] % len;
    }
}
return -1;

with

int duplicate = -1;
for(int i = 0; i < len; i++) {
    if(a[i] < 0) {
        a[i] = -a[i];
        if(duplicate == -1) {
            duplicate = a[i] % len;
        }
    }
    a[i] %= len;
}
return duplicate;