Java interview question: Check array for duplicate values in one pass

This question should be asked more precisely: How can array of size N filled with numbers up to N (0 to N – 1) be scanned for duplicate values (or more) with one scan (O(n))?

The answer lies in the body of the question: The fact that the array is filled with numbers up to N only, implies that a helper array of size N can be used to store the number of times each number appears in the first array. The value of the number in the first array is used as an index in the helper array. For example, if the first value in the array is: 5, then the 5th element in the helper array is incremented by 1. Of course, before incrementing the value in the helper array, we check if it is larger than 0. If it is larger than 0, the value of the first array was already counted once, and this current value is a duplicate.

The code of such method is very simple, lets have a look:

public class ArrayDuplicates {
  public static boolean isDuplicate(int[] arr)
  {
    int size = arr.length;
    int[] helperArr = new int[size];
    for (int i = 0; i < size; i++)
    {
      if (helperArr[arr[i]]++ > 0)
      {
        return true;
      }
    }
    return false;
  }
  public static void main(String[] args)
  {
    System.out.println(isDuplicate(new int[] { 2, 1, 0 }));
    System.out.println(isDuplicate(new int[] { 2, 0, 2 }));
  }
}

Note, that incrementing the index of the helper array (according to the value from the first array) and checking if we have already counted this number is all done the “if” sentence.