Leetcode: Maximum Gap

Maximum Gap


<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/maximum-gap“><img align=”right” width=”200″ height=”183″ src=”github.png” /></a>

Similar Problems:


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))

Walk Through Testdata

Leetcode: Maximum Gap

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
// Blog link: https://code.dennyzhang.com/maximum-gap

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.