Solution

Approach #1 Comparison Sorting [Accepted]

Intuition

Do what the question says.

Algorithm

Sort the entire array. Then iterate over it to find the maximum gap between two successive elements.

Complexity Analysis

\n
• \n

  Time complexity: $$O(n \\cdot log(n))$$ .

  \n

  Time taken to sort the array is $$O(n \\cdot log(n))$$ (average case). Time taken for linear iteration through the array is of $$O(n)$$ complexity. Hence overall time complexity is $$O(n \\cdot log(n))$$ .

  \n
\n
• \n

  Space complexity: No extra space needed, other than the input array (since sorting can usually be done in-place).

  \n
\n

Approach #2 Radix Sort [Accepted]

Algorithm

This approach is similar to Approach #1, except we use Radix Sort instead of a traditional comparison sort.

Complexity Analysis

\n
• \n

  Time complexity: $$O(d \\cdot (n + k)) \\approx O(n)$$ .

  \n

  Since a linear iteration over the array (once it is sorted) is of linear (i.e. $$O(n)$$ ) complexity, the performance of this approach is limited by the performance of Radix sort.

  \n

  Radix sort uses Counting sort as a subroutine.

  \n
  \n
  • \n

    Counting sort runs in $$O(n + k)$$ time (where $$k$$ is the radix or base of the digits comprising the $$n$$ elements in the array). If $$k \\leq O(n)$$ , Counting sort would run in linear time. In our case, the radix is fixed (i.e. $$k = 10$$ ). Hence our Counting sort subroutine runs in $$O(n)$$ linear time.

    \n
  \n
  • \n

    Radix sort works by running $$d$$ passes of the Counting sort subroutine (where the elements are composed of, maximally, $$d$$ digits). Hence effective runtime of Radix sort would be $$O(d \\cdot (n + k))$$ . However, in our case an element can, maximally, be the maximum 32-bit signed integer 2,147,483,647. Hence $$d \\leq 10$$ is a constant.

    \n
  \n
  \n

  Thus Radix sort has a runtime performance complexity of about $$O(n)$$ for reasonably large input.

  \n
\n
• \n

  Space complexity: $$O(n + k) \\approx O(n)$$ extra space.

  \n

  Counting sort requires $$O(k)$$ extra space. Radix sort requires an auxiliary array of the same size as input array. However given that $$k$$ is a small fixed constant, the space required by Counting sort can be ignored for reasonably large input.

  \n
\n

Approach #3 Buckets and The Pigeonhole Principle [Accepted]

Intuition

Sorting an entire array can be costly. At worst, it requires comparing each element with every other element.\nWhat if we didn\'t need to compare all pairs of elements? That would be possible if we could somehow divide the elements into representative groups, or rather, buckets. Then we would only need to compare these buckets.

\n

Digression: The Pigeonhole Principle\nThe Pigeonhole Principle states that if $$n$$ items are put into $$m$$ containers, with $$n > m$$ , then at least one container must contain more than one item.

\n

Suppose for each of the $$n$$ elements in our array, there was a bucket. Then each element would occupy one bucket. Now what if we reduced, the number of buckets? Some buckets would have to accommodate more than one element.

Now let\'s talk about the gaps between the elements. Let\'s take the best case, where all elements of the array are sorted and have a uniform gap between them. This means every adjacent pair of elements differ by the same constant value. So for $$n$$ elements of the array, there are $$n-1$$ gaps, each of width, say, $$t$$ . It is trivial to deduce that $$t = (max - min)/(n-1)$$ (where $$max$$ and $$min$$ are the minimum and maximum elements of the array). This width is the maximal width/gap between two adjacent elements in the array; precisely the quantity we are looking for!

One can safely argue that this value of $$t$$ , is in fact, the smallest value that $$t$$ can ever accomplish of any array with the same number of elements (i.e. $$n$$ ) and the same range (i.e. $$(max - min)$$ ). To test this fact, you can start with a uniform width array (as described above) and try to reduce the gap between any two adjacent elements. If you reduce the gap between $$arr[i-1]$$ and $$arr[i]$$ to some value $$t - p$$ , then you will notice that the gap between $$arr[i]$$ and $$arr[i+1]$$ would have increased to $$t + p$$ . Hence the maximum attainable gap would have become $$t + p$$ from $$t$$ . Thus the value of the maximum gap $$t$$ can only increase.

Buckets!

Coming back to our problem, we have already established by application of the Pigeonhole Principle, that if we used buckets instead of individual elements as our base for comparison, the number of comparisons would reduce if we could accommodate more than one element in a single bucket. That does not immediately solve the problem though. What if we had to compare elements within a bucket? We would end up no better.

So the current motivation remains: somehow, if we only had to compare among the buckets, and not the elements within the buckets, we would be good. It would also solve our sorting problem: we would just distribute the elements to the right buckets. Since the buckets can be already ordered, and we only compare among buckets, we wouldn\'t have to compare all elements to sort them!

But if we only had buckets to compare, we would have to ensure, that the gap between the buckets itself represent the maximal gap in the input array. How do we go about doing that?

We could do that just by setting the buckets to be smaller than $$t = (max - min)/(n-1)$$ (as described above). Since the gaps (between elements) within the same bucket would only be $$\\leq t$$ , we could deduce that the maximal gap would indeed occur only between two adjacent buckets.

Hence by setting bucket size $$b$$ to be $$1 < b \\leq (max - min)/(n-1)$$ , we can ensure that at least one of the gaps between adjacent buckets would serve as the maximal gap.

Clarifications

A few clarifications are in order:

\n
• \n

  Would the buckets be of uniform size?\nYes. Each of them would be of the same size $$b$$ .

  \n
\n
• \n

  But, then wouldn\'t the gap between them be uniform/constant as well?\nYes it would be. The gap between them would be $$1$$ integer unit wide. That means a two adjacent buckets of size $$3$$ could hold integers with values, say, $$3 - 6$$ and $$7 - 9$$ . We avoid overlapping buckets.

  \n
\n
• \n

  Then what are you talking about when you say the gap between two adjacent buckets could be the maximal gap?\nWhen we are talking about the size of a bucket, we are talking about its holding capacity. That is the range of values the bucket can represent (or hold). However the actual extent of the bucket are determined by the values of the maximum and minimum element a bucket holds. For example a bucket of size $$5$$ could have a capacity to hold values between $$6 - 10$$ . However, if it only holds the elements $$7, 8$$ and $$9$$ , then its actual extent is only $$(9 - 7) + 1 = 3$$ which is not the same as the capacity of the bucket.

  \n
\n
• \n

  Then how do you compare adjacent buckets?\nWe do that by comparing their extents. Thus we compare the minimum element of the next bucket to the maximum element of the current bucket. For example: if we have two buckets of size $$5$$ each, holding elements $$[1, 2, 3]$$ and $$[9, 10]$$ respectively, then the gap between the buckets would essentially refer to the value $$9 - 3 = 6$$ (which is larger than the size of either bucket).

  \n
\n
• \n

  But then aren\'t we comparing elements again?!\nWe are, yes! But only compare about twice the elements as the number of buckets (i.e. the minimum and maximum elements of each bucket). If you followed the above, you would realize that this amount is certainly less than the actual number of elements in the array, given a suitable bucket size was chosen.

  \n
\n

Algorithm

\n
• \n

  We choose a bucket size $$b$$ such that $$1 < b \\leq (max - min)/(n-1)$$ . Let\'s just choose $$b = \\lfloor (max - min)/(n-1) \\rfloor$$ .

  \n
\n
• \n

  Thus all the $$n$$ elements would be divided among $$k = \\lceil (max - min)/b \\rceil$$ buckets.

  \n
\n
• \n

  Hence the $$i^{th}$$ bucket would hold the range of values: $$\\bigg [min + (i-1) * b, \\space min + i*b \\bigg )$$ (1-based indexing).

  \n
\n
• \n

  It is trivial to calculate the index of the bucket to which a particular element belongs. That is given by $$\\lfloor (num - min)/b \\rfloor$$ (0-based indexing) where $$num$$ is the element in question.

  \n
\n
• \n

  Once all $$n$$ elements have been distributed, we compare $$k-1$$ adjacent bucket pairs to find the maximum gap.

  \n
\n

Complexity Analysis

\n
• \n

  Time complexity: $$O(n + b) \\approx O(n)$$ .

  \n

  Distributing the elements of the array takes one linear pass (i.e. $$O(n)$$ complexity). Finding the maximum gap among the buckets takes a linear pass over the bucket storage (i.e. $$O(b)$$ complexity). Hence overall process takes linear runtime.

  \n
\n
• \n

  Space complexity: $$O(2*b) \\approx O(b)$$ extra space.

  \n

  Each bucket stores a maximum and a minimum element. Hence extra space linear to the number of buckets is required.

  \n
\n

Analysis written by @babhishek21. Shout-out to @zkfairytale, @teddyyyy and @lhearen!