Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Solution:
1. public class Solution {
2. public int maximumGap(int[] nums) {
3. if (nums == null || nums.length < 2) {
4. return 0;
5. }
6. 7. int n = nums.length;
8. 9. // m is the maximal number in nums
10. int m = nums[0];
11. for (int i = 1; i < n; i++) {
12. m = Math.max(m, nums[i]);
13. }
14. 15. int exp = 1; // 1, 10, 100, 1000 ...
16. int R = 10; // 10 digits
17. 18. int[] aux = new int[n];
19. 20. while (m / exp > 0) { // Go through all digits from LSB to MSB
21. int[] count = new int[R];
22. 23. for (int i = 0; i < n; i++) {
24. count[(nums[i] / exp) % 10]++;
25. }
26. 27. for (int i = 1; i < R; i++) {
28. count[i] += count[i - 1];
29. }
30. 31. for (int i = n - 1; i >= 0; i--) {
32. aux[--count[(nums[i] / exp) % 10]] = nums[i];
33. }
34. 35. for (int i = 0; i < n; i++) {
36. nums[i] = aux[i];
37. }
38. 39. exp *= 10;
40. }
41. 42. int max = 0;
43. for (int i = 1; i < aux.length; i++) {
44. max = Math.max(max, aux[i] - aux[i - 1]);
45. }
46. 47. return max;
48. }
49. }