# C++ 12ms, defeat 94% submission, O(n) time complexity

``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.size() == 0) return 0;

int ans = 1, now = 1, last = nums[0];
for (int i=1; i<nums.size(); i++) {
if (nums[i] == nums[i-1]) continue;
if (nums[i] == last+1) {
now++;
ans = max(ans, now);
last++;
}else {
now = 1;
last = nums[i];
}
}
return ans;
}

int n = nums.size();
t0 = new int[n+4];
t1 = new int[n+4];
pos = new int[n+4];
neg = new int[n+4];

int n1=0, n2=0, maxn=nums[0], minn=nums[0];
for (int i=0; i<n; i++) {
if (nums[i] >= 0) {
pos[n1++] = nums[i];
}else {
neg[n2++] = nums[i];
}
maxn = max(maxn, nums[i]);
minn = min(minn, nums[i]);
}

sort(pos, n1, last_bit(maxn, 1));
sort(neg, n2, last_bit(minn, 0));

for (int i=0; i<n2; i++) {
nums[i] = neg[i];
}
for (int i=0; i<n1; i++) {
nums[n2+i] = pos[i];
}

delete[] t0;
delete[] t1;
delete[] pos;
delete[] neg;
}

int last_bit(int x, int bit) {
int i;
for (i=31; i>=0; i--) {
int t = (((unsigned int)x) >> i) & 0x1;
if (t == bit) return i;
}
return 0;
}

void sort(int A[], int n, int max_bit_pos) {
for (int i=0; i<=max_bit_pos; i++) {
int n0 = 0, n1 = 0;

for (int j=0; j<n; j++) {
if (((unsigned int)A[j] >> i) & 0x1) {
t1[n1++] = A[j];
}else {
t0[n0++] = A[j];
}
}

for (int j=0; j<n0; j++) {
A[j] = t0[j];
}
for (int j=0; j<n1; j++) {
A[n0+j] = t1[j];
}
}
}

int *t0, *t1, *pos, *neg;
};``````

• After sorting this problem seems no longer a problem, I think this is not a trick instead it's against the requirement O(n).

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