# Leetcode – 164. Maximum Gap

Given an integer array `nums`

, return *the maximum difference between two successive elements in their sorted form*. If the array contains less than two elements, return `0`

.

You must write an algorithm that **runs in linear time** and uses **linear extra space.**

**Example 1:**

Input:nums = [3,6,9,1]Output:3Explanation:The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

**Example 2:**

Input:nums = [10]Output:0Explanation:The array contains less than 2 elements, therefore return 0.

**Constraints:**

`1 <= nums.length <= 10`

^{4}`0 <= nums[i] <= 10`

^{9}

**Solution:**

The main problem is we can’t sort the array as it will take n log(n) complexity, but as asked we have to do this in O(n).

We will be solving this question using ** The Pigeonhole Principle.** (

**Recommended**: Watch this video)

The **pigeonhole principle** states that “if **n** items are put into m containers, with** n>m**, then at least one container must contain more than one item.” Sounds simple but it has many applications.

To understand the solution, you must be first familiar with **bucket sort**.

- For example, we set the bucket size to be 10, those numbers can be put into the above buckets. If we set the bucket size clever(relatively small), we can ensure that the max gap cannot be in the same bucket. In the worst-case, each successive numbers have the same gap. For example, we have 1, 3, 5 the gap and the max gap is
`(5 - 1) / 2`

. Largest – Smallest, two gaps. - Based on this, we only need to compare the max number in this bucket and the min number in the next bucket to get the relatively large gap and find out which two buckets have the largest gap.

Table of Contents

### Step 1 – Find maximum and minimum elements from the input

int max = nums[0]; int min = nums[0]; for(int num:nums){ max = Math.max(num, max) ; min = Math.min(num, min); }

### Step 2 – Create min and max bucket

int[] maxBucket = new int[n]; int[] minBucket = new int[n]; Arrays.fill(maxBucket,Integer.MIN_VALUE); Arrays.fill(minBucket,Integer.MAX_VALUE);

### Step 3 – Derive bucket size

int bucketSize = (int)Math.ceil((double)(max-min)/(n - 1));

### Step 4 – Fill up min and max elements belongs to buckets

As we can’t have the maximum gap lies in the same bucket (because at maximum gap we can have is bucketSize-1, so we will be maintaining only min and max elements in the respective buckets.

for(int num: nums){ int bucketIndex = (num-min) / bucketSize; maxBucket[bucketIndex] = Math.max(num,maxBucket[bucketIndex]); minBucket[bucketIndex] = Math.min(num,minBucket[bucketIndex]); }

## Step 5 – Finding out the maximum gap

int maxGap = 0; int previous = maxBucket[0]; for(int i=1;i<n;i++){ if(minBucket[i] == Integer.MAX_VALUE) continue; maxGap = Math.max(maxGap,minBucket[i] - previous); previous = maxBucket[i]; }

### Complete Code

class Solution { public int maximumGap(int[] nums) { int n = nums.length; if(n < 2) return 0; int max,min = nums[0]; int min = nums[0]; for(int num:nums){ max = Math.max(num, max) ; min = Math.min(num, min); } if(max == min) return 0; int[] maxBucket = new int[n]; int[] minBucket = new int[n]; Arrays.fill(maxBucket,Integer.MIN_VALUE); Arrays.fill(minBucket,Integer.MAX_VALUE); int bucketSize = (int)Math.ceil((double)(max-min)/(n -1)); for(int num: nums){ int bucketIndex = (num-min) / bucketSize; maxBucket[bucketIndex] = Math.max(num,maxBucket[bucketIndex]); minBucket[bucketIndex] = Math.min(num,minBucket[bucketIndex]); } int maxGap = 0; int previous = maxBucket[0]; for(int i=1;i<n;i++){ if(minBucket[i] == Integer.MAX_VALUE) continue; maxGap = Math.max(maxGap,minBucket[i] - previous); previous = maxBucket[i]; } return maxGap; } }

### Complexity

**Time complexity: **O(n)**Space complexity:** O(n)