C# - use counting array - O(n) time, O(n) space with explaination


  • 0

    The max H value you could have is limited by the number of citations or the highest citation number. Build a frequency/counting array and you can put all the citation values that are greater than the number of citations into the last bucket. Ideally you'd size your counting array based on the lesser of the number of citations or the highest valued citation, but here we just take number of citations. This step takes O(n) extra space and O(n) time.

    Once you have the counting array, walk from the tail backwards keeping track of the sum of the citations. Once the sum of citations equals or exceeds the position in the array you have found H.

        public int HIndex(int[] citations) 
        {
            int max = citations.Length;
            int[] counts = new int[citations.Length + 1];
            
            for (int i = 0; i < citations.Length; i++)
            {
                if (citations[i] > max) counts[max]++;
                else counts[citations[i]]++;
            }
            
            int sum = 0;
            for (int i = counts.Length - 1; i >= 0; i--)
            {
                sum += counts[i];
                if (sum >= i) return i;
            }
            return 0;
        }
    

Log in to reply
 

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