package com.freetymekiyan.algorithms.level.medium;

/**
 * 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.
 * <p>
 * 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."
 * <p>
 * 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.
 * <p>
 * Note: If there are several possible values for h, the maximum one is taken as the h-index.
 * <p>
 * Hint:
 * <p>
 * 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.
 * <p>
 * Company Tags: Bloomberg, Google, Facebook
 * Tags: Hash Table, Sort
 * Similar Problems: (M) H-Index II
 */
public class HIndex {

    /**
     * Bucket sort.
     * Suppose n is the number of papers.
     * H can be at most n when a person has n papers and all of them have more than n citations.
     * To find a number h that h of his n papers have >= h citations, put papers in buckets.
     * All papers have >= n citations put into bucket n.
     * Papers have i citations put into bucket i.
     * Then count backwards.
     * The first number i that has total papers >= i is the answer.
     */
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] buckets = new int[n + 1];
        for (int c : citations) {
            if (c >= n) {
                buckets[n]++;
            } else {
                buckets[c]++;
            }
        }
        int papers = 0;
        for (int i = n; i >= 0; i--) {
            papers += buckets[i];
            if (papers >= i) {
                return i;
            }
        }
        return 0;
    }
}

@@ -49,16 +49,39 @@
 m;%0A%0A/**%0A
+ * 274. H-Index%0A * %3Cp%3E%0A
  * Given
@@ -1173,330 +1173,653 @@
   * 
-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
+We actually want to know how many papers are there with %3E= some h.%0A     * Given an h, we can query some data structure to achieve that.%0A     * Let's assume there is a method m that takes h and outputs m(h).%0A     * m(i) = # of papers that have at least i citations.%0A     * If c(i) is the # of papers that have exactly i citations,%0A     * m(i) = c(i) + c(i+1) + ... + c(N), 0 %3C= i %3C= N.%0A     * When we calculate m(i), we would calculate c(N) multiple times, which is duplicate.%0A     * So we can store i-%3Ec(i) somewhere. That leads to a Map%3CInteger, Integer%3E.%0A     * And H-Index can be at most N when a person has N papers and all of them
  have 
-i
+%3E= N
  cit
@@ -1828,54 +1828,164 @@
 ions
- put into bucket i.%0A     * Then count backward
+.%0A     * Now we know 0 %3C= i %3C= N. That further simplifies the map to an integer array.%0A     * We build this array. Go backwards to accumulate the # of paper
 s.%0A 
@@ -1994,67 +1994,83 @@
   * 
-The first number i that has total papers %3E= i is the answer
+When the # of papers %3E= i, return i.%0A     * If there is no such i, return 0
 .%0A  
@@ -2164,21 +2164,20 @@
   int%5B%5D 
-bucke
+coun
 ts = new
@@ -2242,17 +2242,16 @@
  if (c %3E
-=
  n) %7B%0A  
@@ -2264,21 +2264,20 @@
         
-bucke
+coun
 ts%5Bn%5D++;
@@ -2314,21 +2314,20 @@
         
-bucke
+coun
 ts%5Bc%5D++;
@@ -2440,13 +2440,12 @@
  += 
-bucke
+coun
 ts%5Bi
@@ -2553,9 +2553,8 @@
 %0A    %7D%0A%7D
-%0A

update 274. H-Index with better proof