# Alternative linear space/time solution, recursive Radix sort in binary

• This solution is quite not the optimal one, but also fits in linear space and time requirement. The idea is the same as in radix sort solution, but here I sorted the numbers by bits instead of decimal digits.

``````public class Solution {
List<Integer> sorted;
public int maximumGap(int[] nums) {
if(nums.length<2) return 0;
System.out.println(nums.length);
sorted =  new ArrayList<>(nums.length);
bitSort(0, nums.length, new ArrayList<>(), new ArrayList<>(), 31);
int max = 0;
for(int i = 0;i<nums.length-1;i++) max = Integer.max(max, sorted.get(i+1)-sorted.get(i));
return max;
}

public void bitSort(int s, int e,  List<Integer> left, List<Integer> right, int p){
if(p<0 || e<=s) return;
left.clear();
right.clear();
int x = (1<<p);
for(int i = s;i<e;i++){
int num = sorted.get(i);
}

for(int i = s;i<s+left.size();i++){
sorted.set(i, left.get(i-s));
}
for(int i = s+left.size();i<s+left.size()+right.size();i++){
sorted.set(i, right.get(i-s-left.size()));
}
int leftSize = left.size(), rightSize = right.size();
bitSort(s, s+leftSize, left, right, p-1);
bitSort(s+leftSize, e,  left, right, p-1);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.