Create maximum-gap.py

kamyu104 · kamyu104 · commit 58a3a49c4e53 · 2015-05-31T02:59:31.000+08:00
diff --git a/Python/maximum-gap.py b/Python/maximum-gap.py
@@ -0,0 +1,39 @@
+# Time:  O(n)
+# Space: O(n)
+
+class Solution:
+     # @param numss: a list of integers
+     # @return: the maximum difference
+    def maximumGap(self, nums):
+        if len(nums) < 2:
+            return 0
+        
+        # Init bucket.
+        max_val, min_val = max(nums), min(nums)
+        gap = max(1, (max_val - min_val) / (len(nums) - 1))
+        bucket_size = (max_val - min_val) / gap + 1
+        bucket = [{'min':float("inf"), 'max':float("-inf")} \
+                    for _ in xrange(bucket_size)]
+
+        # Find the bucket where the n should be put.
+        for n in nums:
+            # min_val / max_val is in the first / last bucket.
+            if n in (max_val, min_val):
+                continue      
+            i = (n - min_val) / gap
+            bucket[i]['min'] = min(bucket[i]['min'], n)
+            bucket[i]['max'] = max(bucket[i]['max'], n)
+        
+        # Count each bucket gap between the first and the last bucket.
+        max_gap, pre_bucket_max = 0, min_val
+        for i in xrange(bucket_size):
+            # Skip the bucket it empty.
+            if bucket[i]['min'] == float("inf") and \
+                bucket[i]['max'] == float("-inf"):
+                continue
+            max_gap = max(max_gap, bucket[i]['min'] - pre_bucket_max)
+            pre_bucket_max = bucket[i]['max']
+        # Count the last bucket.
+        max_gap = max(max_gap, max_val - pre_bucket_max) 
+        
+        return max_gap
