Since they say linear time, sorting is not an option,
So, we need some solution in linear time.
The solution for this, uses a bucket sort approach based on the pigeonhole principle,
where we distribute elements into buckets and compute the maximum gap
between adjacent buckets instead of sorting the entire array.
Here’s how it works,
In the array, we get the min and max element,
Then, we can see that, gives us the minimum possible maximum gap. This is basically if all elements were evenly spaced.
Now, the real maximum gap must be this value.
And any gap larger than this must occur between groups, not inside a group.
What does that mean?
Consider this,