## Algorithm

Problem Name: 164. Maximum Gap

Given an integer array `nums`, return the maximum difference between two successive elements in its 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: 3
Explanation: 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: 0
Explanation: The array contains less than 2 elements, therefore return 0.
```

Constraints:

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 109`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maximumGap(int num[], int n) {
if (n  <  2) return 0;

int *sorted_num = (int *)calloc(n, sizeof(int));
int *temp = (int *)calloc(n, sizeof(int));

memcpy(sorted_num, num, sizeof(int) * n);

int i, j;
int shift;
for (shift = 0; shift  <  32; shift += 8) {
int count[0x100] = {};

for (i = 0; i  <  n; i++) {
count[(sorted_num[i] >> shift) & 0xFF] ++;
}

int idx = 0, t = 0;
for (j = 0; j  <  0x100; j++) {
t = count[j];
count[j] = idx;
idx += t;
}

for (i = 0; i  <  n; i++) {
temp[count[(sorted_num[i] >> shift) & 0xFF] ++] = sorted_num[i];
}

int *p = sorted_num;
sorted_num = temp;
temp = p;
}

int max_diff = 0;
for (i = 1; i  <  n; i++) {
if (sorted_num[i] - sorted_num[i - 1] > max_diff) {
max_diff = sorted_num[i] - sorted_num[i - 1];
}
}

free(sorted_num);
free(temp);
return max_diff;
}

int main() {
int A[] = { 4, 5, 3, 2, 9, 12, 32, 5 };

/* should be 20 = abs(12 - 32) */
printf("%d\n", maximumGap(A, sizeof(A)/sizeof(A[0])));

return 0;
}
``````
Copy The Code &

Input

cmd
nums = [3,6,9,1]

Output

cmd
3

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maximumGap = function (nums) {
if (nums.length < 2) return
let max = 0
nums = nums.sort(function (a, b) {
return a - b
})
for (let i = 1; i  <  nums.length; i++) {
if (nums[i] - nums[i - 1] > max) max = nums[i] - nums[i - 1]
}
return max
}
``````
Copy The Code &

Input

cmd
nums = [3,6,9,1]

Output

cmd
3

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maximumGap(self, nums):
if len(nums) < 2:
return 0
n, mn, mx= len(nums), min(nums), max(nums)
bSize = max(1, (mx - mn) // n + 1)
bNum = (mx - mn) // bSize + 1
buckets = [[float("inf"), -float("inf")] for _ in range(bNum)]
for num in nums:
ind = (num - mn) // bSize
if num < buckets[ind][0]:
buckets[ind][0] = num
if num > buckets[ind][1]:
buckets[ind][1] = num
gap = 0
for i in range(1, bNum):
if buckets[i] == [float("inf"), -float("inf")]:
buckets[i] = buckets[i - 1]
gap = max(gap , buckets[i][0] - buckets[i - 1][1])
return gap
``````
Copy The Code &

Input

cmd
nums = [10]