Leetcode 164: Maximum Gap

I used bucket sort (pigeonhole principle). So we create nums.size() buckets and we spread them out at a distance that is equal to uniformly distributed set spread (which is the smallest maximum gap we could possibly have). For each bucket we store minimum and maximum values. We go through each number setting the max/min of the appropriate bucket for it. Then we go through all buckets figuring out the biggest gap between the buckets. Beware of empty buckets, which we skip. It is also possible to solve with a radix sort.

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *