Is there any way to compare each element in an array using a single loop?

Question

I need to print the least difference between any two elements of an int array.

each element of array A is less than equal to its length.

1 <= A[i] <= A.length;

I have tried this below given approach in Java - But this takes more than 1 second to find results when array size is given ~10^5.

I think it may be a naive approach. Is there any way i can optimize it further? Can it be done in O(n) time complexity?

static int findResult(int[] arr)
        {
                 int max =  Integer.MAX_VALUE;
                 HashSet<Integer> hs = new HashSet<Integer>();
                 for(int obj : arr)
                 {
                     hs.add(obj);
                 }
                if(hs.size()==1 )
                {
                    return 0;             // if all elements are same
                }
                 for(int i=0; i<arr.length; i++)
                 {  
                     for(int j=i+1; j<arr.length; j++)
                     {
                         int value = Math.abs(a[i]-a[j]);
                         if(value<max)
                         {
                            max = value;
                         }

                      }         
                }
        return max;  // returns the smallest positive difference
    }

Answer 1

With 1≤x_i≤n: O(n)

Since for every x_i it holds that 1≤x_i≤n, it holds that, due to the pigeonhole principle, either all values exist exactly once, or a value exists two or more times.

In the former case, the difference is 1 (for an array larger than 1 element), in the latter case, the result is 0, since then there are two items that are exactly equal.

We can thus iterate over the array and keep track of the numbers. If a number already exists once, we return 0, otherwise, we return 1, like:

// only if it holds that for all i, 1 <= arr[i] <= arr.length
static int findResult(int[] arr) {
    bool[] found = new bool[arr.length]
    for(int i = 0; i < arr.length; i++) {
        if(found[arr[i]-1]) {
            return 0;
        } else {
            found[arr[i]-1] = true;
        }
    }
    return 1;
}

For a random array that satisfies the condition with n elements, in n!/nⁿ of the cases, it will return 1, and in the other cases, it will return 0, so the average over random input is n!/nⁿ. As n grows larger, it becomes very unlikely that there are no "collisions", and thus, as @YvesDaoust says, the approximation of 0 is very likely.

Without 1≤x_i≤n: O(n log n)

In case we drop the constraint, we can first sort the array, and in that case, we iterate over consecutive elements:

static int findResult(int[] arr) {
    Arrays.sort(arr);
    int dmin = arr[1] - arr[0];
    for(int i = 2; i < arr.length; i++) {
        int d = arr[i] - arr[i-1];
        if(d < dmin) {
            if(d == 0) {
                return 0;
            }
            dmin = d;
        }
    }
    return dmin;
}