# Is there a O(n) time solution?

• I see most posts use std::sort( ) which is O(nlgn). I tried to use a modified radix sort but failed with the last two tests and I don't know the reason. Could someone point it out? Is there a O(n) solution possible??

``````class Solution {
public:
int getDig(int num, int i){
string s=std::to_string(num);
if(i>s.size()-1){
if(s.back()-s[0]==1) return s[0]+1-'0';
else return s[0]-'0';
}
return s[i]-'0';
}

void countSort(vector<int>& nums, int x)
{
vector<int> res(nums.size(),0);
int i, count[11] = {0};
for (i = 0; i < nums.size(); i++) count[ getDig(nums[i], x) ]++;
for (i = 0; i <=10; i++) count[i] += count[i - 1];
for (i = nums.size() - 1; i >= 0; i--){
res[count[ getDig(nums[i], x) ] - 1] = nums[i];
count[ getDig(nums[i], x) ]--;
}
for (i = 0; i < nums.size(); i++) nums[i] = res[i];
}

string largestNumber(vector<int>& nums) {
int maxNum=nums[0];
for(int i=1;i<nums.size();i++) maxNum=max(maxNum,nums[i]);
int m=0;
while(maxNum){
maxNum/=10;
m++;
}
for (int x = m-1; x>=0; x--) countSort(nums, x);
string res="";
for (int i=nums.size()-1;i>=0;i--) res+=std::to_string(nums[i]);
while(res[0]=='0'&&res.size()>1) res.erase(res.begin());
return res;
}
};``````

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