Maximum Gap – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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
C++ Maximum Gap LeetCode Solution
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
auto lu = minmax_element(nums.begin(), nums.end());
int l = *lu.first, u = *lu.second;
int gap = max((u - l) / (n - 1), 1);
int m = (u - l) / gap + 1;
vector<int> bucketsMin(m, INT_MAX);
vector<int> bucketsMax(m, INT_MIN);
for (int num : nums) {
int k = (num - l) / gap;
if (num < bucketsMin[k]) bucketsMin[k] = num;
if (num > bucketsMax[k]) bucketsMax[k] = num;
}
int i = 0, j;
gap = bucketsMax[0] - bucketsMin[0];
while (i < m) {
j = i + 1;
while (j < m && bucketsMin[j] == INT_MAX && bucketsMax[j] == INT_MIN)
j++;
if (j == m) break;
gap = max(gap, bucketsMin[j] - bucketsMax[i]);
i = j;
}
return gap;
}
};
Java Maximum Gap LeetCode Solution
public class Solution {
public int maximumGap(int[] num) {
if (num == null || num.length < 2)
return 0;
// get the max and min value of the array
int min = num[0];
int max = num[0];
for (int i:num) {
min = Math.min(min, i);
max = Math.max(max, i);
}
// the minimum possibale gap, ceiling of the integer division
int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket
Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
// put numbers into buckets
for (int i:num) {
if (i == min || i == max)
continue;
int idx = (i - min) / gap; // index of the right position in the buckets
bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
}
// scan the buckets for the max gap
int maxGap = Integer.MIN_VALUE;
int previous = min;
for (int i = 0; i < num.length - 1; i++) {
if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
// empty bucket
continue;
// min value minus the previous value is the current gap
maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
// update previous bucket value
previous = bucketsMAX[i];
}
maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
return maxGap;
}
}
Python 3 Maximum Gap LeetCode Solution
class Solution:
def maximumGap(self, nums):
lo, hi, n = min(nums), max(nums), len(nums)
if n <= 2 or hi == lo: return hi - lo
B = defaultdict(list)
for num in nums:
ind = n-2 if num == hi else (num - lo)*(n-1)//(hi-lo)
B[ind].append(num)
cands = [[min(B[i]), max(B[i])] for i in range(n-1) if B[i]]
return max(y[0]-x[1] for x,y in zip(cands, cands[1:]))
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below