Maximum Gap

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #classicm, #bucketsort, #inspiring

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution: bucket sort

**General Thinkings:**

Put each element into a list of buckets. Each bucket track the min and max. The scan the bucket kist, we get the maximum gap. Some improvements: To get the mininum bucket count, we avoid placing min and max into any buckets. Bucket count: n-1, bucket size: int((max-min)/(n-1))

**Key Observations:**

- Duplicate elements doesn't matter - Instead of total order, we maintain partial order in bucket-sort. Actually we don't even sort. We can compare items with pilots

// https://code.dennyzhang.com/maximum-gap