Maximum adjacent difference in an array in its sorted form

/Maximum adjacent difference in an array in its sorted form

Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n). For example

Input : arr[] = {1, 10, 5}
Output : 5

Sorted array would be {1, 5, 10} and
maximum adjacent difference would be 
10 - 5 = 5

An efficient solution is based on idea of Pigeonhole sorting. If the array contains N numbers within a contagious sequence of numbers with values between a min and max value (inclusive) then the maximum gap is one. Now, in real problem many of these numbers will be missing. It may happen that some range of values are missing in the sequence and thus creating gaps. If we can identify such missing ranges in a cheap way then we can solve this problem in O(n).

The idea is to bucketize the values between min and max value (exclusive) of the given array into a set of equal sized buckets. Each of such empty buckets will create a gap of size equals to the difference between max value in the previous non-empty bucket and the minimum value in the next non-empty bucket. 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. The maximum gap would be the difference of maximum value in previous bucket and minimum value in next bucket, this condition makes sure that element are adjacent in the sorted array.

April 20th, 2019|Categories: Data Structure|
avatar
  Subscribe  
Notify of