https://leetcode.com/problems/maximum-gap/description/

Tag: Array/List

Key Points:

1. The given array is not sorted. Sorting normally takes nLog(n) time, longer than linear time.

2. One common method to process integer array is to iterate the array value from minimum number to maximum number in the array, instead of the array index. The time complexity will be O(n + k) where k is the distance between max number and min number. It won’t be as fast for large k, e.g. [1, 10,000,000]

3. Pigeonhole Principle. For this problem, assuming there are n numbers ranging from min to max, if the whole range is averagely sliced into n segments and the n numbers are bucketed into each segment, the minimum gap appears when each number are evenly placed, resulting in each segment has only one number. Whenever a number moves closer to its neighbor, the gap from the other neighbor becomes larger. This implies the max gap always must occurs across different segments. This comes to our third solution with linear time complexity

   

Solution: Iterate by the number instead of array index

def maximumGap(self, nums: List[int]) -> int:
	  if len(nums) < 2:
        return 0
	        
		nums_set = set(nums)
		max_num = max(nums)
		min_num = min(nums)
		
		res = 0
		lower = upper = min_num
		for curr in range(min_num, max_num+1):
				# If current value doesn't exist in the array,
				# found a gap and keep moving upper until the boundary
		    if curr not in nums_set:
		        upper = curr
		    # If current value exists in the array, two cases
		    else:
				    # No gap from previous value
		        if lower == upper:
		            lower = upper = curr
		        # Found the boundary of the gap, update result
		        else:
		            res = max(res, upper - lower + 1)
		            lower = upper = curr
		return res

Solution: Pigeonhole Principle

def maximumGap(self, nums: List[int]) -> int:
	  max_num = max(nums)
	  min_num = min(nums)
	
		# Dedup, ensure range is not smaller than the length of array
	  num_set = set(nums)
	  nums = list(num_set)
	
	  if len(nums) < 2:
	      return 0

		# Initiate N buckets(segments) for numbers from min to max
		# Notice the size has a plus 1. Think of the case [0, 5, 8]. 
	  bucket_size =  (max_num - min_num) // len(nums) + 1
	  buckets = [[None] * 3 for _ in range(len(nums))] # [[min, max, used]]

	  for num in nums:
	      idx = (num - min_num) // bucket_size
	      buckets[idx][0] = min(buckets[idx][0], num) if buckets[idx][0] else num
	      buckets[idx][1] = max(buckets[idx][1], num) if buckets[idx][1] else num
	      buckets[idx][2] = True
	  
	  # As we discussed, the minimum possible maxgap will be the bucket_size
	  # Note 0 or bucket[0][1] - bucket[0][0] all works the same.
	  # The max gap candidate must be across multiple segments
	  res = bucket_size
	  last_max = buckets[0][1]
	  for bucket in buckets:
	      if not bucket[2]:
	          continue
	      res = max(bucket[0] - last_max, res)
	      last_max = bucket[1]
	  return res