# 12ms Radix-Sort (O(n), 256-based) and Counting-Sort (O(n)) Solution for C++

• Here I will use the radix sort, whose time complexity is O(digits * (n + BASE)) = O(4(n + 256)) = O(n), and space complexity is O(n + BASE) = O(n + 256) = O(n).

I treat all numbers as 256-based (rather than traditional 10-based), so we could get rid of the time-consuming "/" and "%" operators, and use the efficient bit-wise operators like ">>" and "&" instead.

For a 32-bit non-negative integer, it contains at most 4 digits (256-based), as illustrated below:

INT_MAX = 0x 7F[digit 3] FF[digit 2] FF[digit 1] FF[dgit 0] (256-based)

``````class Solution {
private:
const int BASE = 256;
const int INT_BASESIZE = sizeof(int) * BASE;
int n = 0;
int *numCounts = nullptr;
int *keys = nullptr;

inline void countingSort(vector<int> &source, vector<int> &target, int digitIndex) {
memset(numCounts, 0, INT_BASESIZE);
for (int i = 0; i < n; i++) {
keys[i] = (source[i] >> digitIndex) & 0xFF;
numCounts[keys[i]]++;
}
for (int i = 1; i < BASE; i++)
numCounts[i] += numCounts[i - 1];
for (int i = n - 1; i >= 0; i--)
target[--numCounts[keys[i]]] = source[i];
}

public:
int maximumGap(vector<int> &num) {
n = num.size();
if (n < 2) return 0;
numCounts = new int[BASE];
keys = new int[n];

vector<int> num2(n);
countingSort(num, num2, 0);
countingSort(num2, num, 8);
countingSort(num, num2, 16);
countingSort(num2, num, 24);

int maxGap = 0;
for (int i = 1; i < n; i++) {
int gap = num[i] - num[i - 1];
if (gap > maxGap)
maxGap = gap;
}
return maxGap;
}
};``````

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