CODEWITHSUNDEEP
algorithmsorting
daremy
daremy

Reputation: 157

Array "maximum difference" algorithm that runs in O(n)?

Given an array of N integers, sort the array, and find the 2 consecutive numbers in the sorted array with the maximum difference.

Example – on input [1,7,3,2] output 4 (the sorted array is [1,2,3,7], and the maximum difference is 7-3=4).

Algorithm A runs in O(NlogN) time.

I need to find an algorithm identical in function to algorithm A, that runs in O(N) time.

Upvotes: 11

Views: 13406

Answers (4)

Visluck
Visluck

Reputation: 47

Now, first try to think if you were already given the minimum value MIN and maximum value MAX in the array of size N, under what circumstances would the max gap be minimum and maximum ?

Obviously, maximum gap will be maximum when all elements are either MIN or MAX making maxgap = MAX - MIN.

Maximum gap will be minimum when all the elements are equally spaced apart between MIN and MAX. Lets say the spacing between them is gap.

So, they are arranged as

MIN, MIN + gap, MIN + 2*gap, MIN + 3*gap, ... MIN + (N-1)*gap 
where

MIN + (N-1)*gap = MAX .

gap = (MAX - MIN) / (N - 1).

So, we know now that our answer will lie in the range [gap, MAX - MIN]. Now, if we know the answer is more than gap, what we do is create buckets of size gap for ranges .

[MIN, MIN + gap), [Min + gap, `MIN` + 2* gap) ... and so on

There will only be (N-1) such buckets. We place the numbers in these buckets based on their value.

If you pick any 2 numbers from a single bucket, their difference will be less than gap, and hence they would never contribute to maxgap ( Remember maxgap >= gap ). We only need to store the largest number and the smallest number in each bucket, and we only look at the numbers across bucket.

Now, we just need to go through the bucket sequentially ( they are already sorted by value ), and get the difference of min_value with max_value of previous bucket with at least one value. We take maximum of all such values.

int maximumGap(const vector<int> &num) {
    if (num.empty() || num.size() < 2) return 0;

    int maxNum = *max_element(num.begin(), num.end());
    int minNum = *min_element(num.begin(), num.end());

    //average gap from minNum to maxNum.
    int gap = (maxNum - minNum - 1) / (num.size() - 1) + 1;

    //number of buckets = num.size() - 1
    vector<int> bucketsMin(num.size() - 1, INT_MAX);
    vector<int> bucketsMax(num.size() - 1, INT_MIN);

    //put into buckets
    for (int i = 0; i < num.size(); i++) 
    {
        if (num[i] != maxNum && num[i] != minNum)
        {
            int buckInd = (num[i] - minNum) / gap;
            bucketsMin[buckInd] = min(bucketsMin[buckInd], num[i]);
            bucketsMax[buckInd] = max(bucketsMax[buckInd], num[i]);
        }
    }
    int maxGap = INT_MIN;
    int previous = minNum;

    for (int i = 0; i < num.size() - 1; i++) 
    {
        if (bucketsMin[i] == INT_MAX && bucketsMax[i] == INT_MIN) continue;   //empty
        //i_th gap is minvalue in i+1_th bucket minus maxvalue in i_th bucket
        maxGap = max(maxGap, bucketsMin[i] - previous);
        previous = bucketsMax[i];
    }
    maxGap = max(maxGap, maxNum - previous);
    return maxGap;
}

Upvotes: 0

Ilya Gazman
Ilya Gazman

Reputation: 32221

  1. Find minimum and maximum
  2. Pick a random number k from the array
  3. Sort the algorithm by placing all the values smaller than k to the left and larger than k to the right.
  4. You know the minimum and the maximum of both of the groups, calculate the gape of the left group assuming that the values are on a strait line. Do the same for the right group.
  5. Go to 2 with the group that got the bigger gape, you know the min and max of that group. Do this until the selected group got no more than 4 values.
  6. You got now a group with only 4 elements, sort and find the solution.

Here is an example of how this algorithm works:

  • Input: 9 5 3 4 12 9 31 17
  • Pick random number: k = 9
  • Sort by smaller and bigger values of k
  • 5 3 4 9 9 12 31 17, k is in index 3
  • Left group gape = (9 + 3) / (4 - 1) = 4
  • Right group gape = (31 + 9) / (5 - 1) = 10
  • We pick the right group 9 9 12 31 17
  • Pick random number: k = 12
  • Sort by smaller and bigger values of k
  • 9 9 12 31 17, k is in index 2
  • Left group gape = (12 + 9) / (3 - 1) = 11.5
  • Right group gape = (31 + 12) / (3 - 1) = 21.5
  • The maximum gape in 12 31 17 is 31 - 17 = 14

My algorithm is very similar to Selection Algorithm for finding the k index value of sorted algorithm in linear time.

Upvotes: -1

zxc
zxc

Reputation: 191

Let the array be X and let n = length(X). Put each element x in bucket number floor((x - min(X)) * (n - 1) / (max(X) - min(X))). The width of each bucket is (max(X) - min(X))/(n - 1) and the maximum adjacent difference is at least that much, so the numbers in question wind up in different buckets. Now all we have to do is consider the pairs where one is the max in bucket i and the other is the min in bucket j where i < j and all buckets k in (i, j) are empty. This is linear time.

Proof that we really need floor: let the function be f(X). If we could compute f(X) in linear time, then surely we could decide in linear time whether

0 < f(X) ≤ (max(X) - min(X))/(length(X) - 1),

i.e., whether the elements of X are evenly spaced and not all identical. Let this predicate be P(X). The support of P has factorial(length(X)) connected components, so the usual Ω(n log n) lower bounds for algebraic models of computation apply.

Upvotes: 15

DigitalRoss
DigitalRoss

Reputation: 146043

Execute a Counting Sort and then scan the result for the largest difference.

Because of the consecutive number requirement, at first glance it seems like any solution will require sorting, and this means at best O(n log n) unless your number range is sufficiently constrained for a Counting Sort. But if it is, you win with O(n).

Upvotes: 4

Related Questions