# C++ O(n) time, O(1) extra space

• 1st loop makes citations[i] = count of occurrence of citation = (i+1) for i from 0 to n-2,
citations[n-1] = count of occurrence of citation >= n.
2nd loop then turns citations[i] to count of occurrence of citation >= i.

"MSB" is as a temporal mark for those i we visited before iterating it and can make sure this algorithm an O(n) in time complexity.

``````#define MSB (1 << 30)
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
if (n == 0) return 0;

for (int k = n-1; k >= 0; ) {
if ((citations[k] & MSB)) {
citations[k--] -= MSB;
continue;
}

int idx = min(citations[k]-1, n-1);
if (idx == k) {
citations[k--] = 1;
} else if (idx > k) {
citations[idx]++;
citations[k--] = 0;
} else {
if (citations[k] > 0) {
if ((citations[idx] & MSB)) {
citations[idx]++;
citations[k--] = 0;
} else {
if (citations[k] == citations[idx]) {
citations[k--] = 0;
citations[idx] = MSB + 2;
} else {
citations[k] = citations[idx];
citations[idx] = MSB + 1;
}
}
} else {
citations[k--] = 0;
}
}
}

for (int k = n-1; k > 0; k--) {
if (citations[k] >= k + 1) {
return (k + 1);
} else {
citations[k - 1] += citations[k];
}
}
return ((citations[0] >= 1) ? 1 : 0);
}
};
``````

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