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, we have a unsorted array, a=[5, 3, 1, 8, 9, 2, 4] of size n=7 then the sorted version is

[1, 2, 3, 4, 5, 8, 9]. The output of the algorithm should be 8-5 = 3.

This is a preview of

The Maximum Gap Problem : Pigeonhole Principle. Read the full post (890 words, estimated 3:34 mins reading time)