Algorithm Puzzles: H-Index

Algorithm Puzzles everyday every week sometimes: H-Index

Puzzle

Puzzle from leetcode:

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Solution

class Solution {
public:
    int hIndex(vector<int>& citations) {
        size_t n = citations.size();

        int citationCount[1001] = {0};

        for(int i = 0; i < n; ++i) {
            citationCount[citations[i]]++;
        }

        int sum = 0;
        int h = 0;

        for(int i = 1000; i >= 0; --i) {
            if(citationCount[i] > 0) {
                sum = sum + citationCount[i];
                if(sum >= i && i >= h) {
                    h = i;
                } else if(sum < i && sum >= h) {
                    h = sum;
                }
            }
        }

        return h;
    }
};

T.C.: O(N)
S.C.: O(1)