Thinking process - Binary Search - O(nlogn)

Range search, from 0 to the length of input array

Using a helper function to check whether the number of numbers that are at learst i exist? find the largest one.

=> get the last element that satisfy a condition

public class Solution {
    public int hIndex(int[] citations) {
        int start = 0;
        int end = citations.length;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;

            if (getNumbers(citations, mid) < mid) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (getNumbers(citations, end) >= end) return end;
        if (getNumbers(citations, start) >= start) return start;

        return 0;
    }

    private int getNumbers(int[] nums, int min) {
        int result = 0;

        for (int num : nums) {
            if (num >= min) {
                result++;
            }
        }

        return result;
    }
}

Thinking process - Bucket sort - O(n) + O(n)

https://discuss.leetcode.com/topic/40765/java-bucket-sort-o-n-solution-with-detail-explanation

You can tell, that the helper function above doing something repeatedly, which can be replaced by a new array

public class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        int[] buckets = new int[len + 1];

        for (int i = 0; i < len; ++i) {
            if (citations[i] >= len) {
                buckets[len] += 1;
            } else {
                buckets[citations[i]] += 1;
            }
        }

        int sum = 0;

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

        return 0;
    }
}