/**
 * Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute
 * the researcher's h-index.
 *
 * According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least
 * h citations each, and the other N − h papers have no more than h citations each."
 *
 * For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had
 * received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and
 * the remaining two with no more than 3 citations each, his h-index is 3.
 *
 * Note: If there are several possible values for h, the maximum one is taken as the h-index.
 *
 * Hint:
 *
 * An easy approach is to sort the array first.
 *
 * What are the possible values of h-index?
 *
 * A faster approach is to use extra space.
 *
 * Tags: Hash Table, Sort
 *
 * Similar Problems: (M) H-Index II
 */
public class HIndex {

    public int hIndex(int[] citations) {
        int len = citations.length;
        int count = 0;

        int[] arr = new int[len + 1];
        for (int i : citations) {
            if (i >= len) {
                arr[len]++;
            } else {
                arr[i]++;
            }
        }

        for (int i = len; i >= 0; i--) {
            count += arr[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }
}

@@ -1,8 +1,60 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A
 /**%0A * G
@@ -194,24 +194,28 @@
  h-index.%0A *
+ %3Cp%3E
 %0A * Accordin
@@ -410,16 +410,20 @@
 ach.%22%0A *
+ %3Cp%3E
 %0A * For 
@@ -728,24 +728,28 @@
 dex is 3.%0A *
+ %3Cp%3E
 %0A * Note: If
@@ -829,24 +829,28 @@
  h-index.%0A *
+ %3Cp%3E
 %0A * Hint:%0A *
@@ -849,16 +849,20 @@
 Hint:%0A *
+ %3Cp%3E
 %0A * An e
@@ -902,19 +902,16 @@
  first.%0A
- *%0A
  * What 
@@ -946,19 +946,16 @@
 -index?%0A
- *%0A
  * A fas
@@ -992,16 +992,65 @@
 pace.%0A *
+ %3Cp%3E%0A * Company Tags: Bloomberg, Google, Facebook
 %0A * Tags
@@ -1072,11 +1072,8 @@
 ort%0A
- *%0A
  * S
@@ -1139,104 +1139,550 @@
     
-public int hIndex(int%5B%5D citations) %7B%0A        int len = citations.length;%0A        int count = 0;%0A
+/**%0A     * Bucket sort.%0A     * Suppose n is the number of papers.%0A     * H can be at most n when a person has n papers and all of them have more than n citations.%0A     * To find a number h that h of his n papers have %3E= h citations, put papers in buckets.%0A     * All papers have %3E= n citations put into bucket n.%0A     * Papers have i citations put into bucket i.%0A     * Then count backwards.%0A     * The first number i that has total papers %3E= i is the answer.%0A     */%0A    public int hIndex(int%5B%5D citations) %7B%0A        int n = citations.length;
 %0A   
@@ -1692,19 +1692,23 @@
   int%5B%5D 
-arr
+buckets
  = new i
@@ -1710,18 +1710,16 @@
 new int%5B
-le
 n + 1%5D;%0A
@@ -1735,17 +1735,17 @@
 or (int 
-i
+c
  : citat
@@ -1772,15 +1772,13 @@
 if (
-i
+c
  %3E= 
-le
 n) %7B
@@ -1798,14 +1798,16 @@
     
-arr%5Ble
+buckets%5B
 n%5D++
@@ -1845,21 +1845,25 @@
         
-arr%5Bi
+buckets%5Bc
 %5D++;%0A   
@@ -1883,16 +1883,39 @@
       %7D%0A
+        int papers = 0;
 %0A       
@@ -1928,18 +1928,16 @@
 int i = 
-le
 n; i %3E= 
@@ -1962,20 +1962,25 @@
     
-count += arr
+papers += buckets
 %5Bi%5D;
@@ -1996,21 +1996,22 @@
     if (
-count
+papers
  %3E= i) %7B

update h index