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

user_5998634 0
Viewed 4887

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
    }
array-algorithms optimization algorithm
3 Answers

With 1≤xi≤n: O(n)

Since for every xi it holds that 1≤xi≤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!/nn of the cases, it will return 1, and in the other cases, it will return 0, so the average over random input is n!/nn. 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≤xi≤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;
}
user_675790

I am assuming that the A's are integer, otherwise the condition 1 <= A[i] <= A.len has no relevance.

Then there is an O(n) solution by using an histogram.

  1. declare an array of counters of size A.length;

  2. count the multiplicities of the elements of A;

  3. scan this histogram to find the closest non-empty bins.

Note that this solution assumes that only nonzero differences are considered. If zero difference counts, then Willem's answer is better.

user_11965490

(Adding to the above answers)

If you need to do this with O(1) extra space, you can use the following trick on the input sequence A:

for a in A[1...n]:        // a is an element in A; A is 1-indexed; 1 <= a <= n
    if M < A[a % M]:
        return 0
    A[a % M] += M
return 1

Here M (> n) is such that M + n doesn't overflow. The trick can be easily modified to use instead an M which is less than -n.

Caveats:

  1. Requires random (i.e. O(1)) access to the elements of A.
  2. Not cache-friendly.
user_75408510
Related