https://leetcode.com/problems/h-index/

hIndex.go

import (
	"fmt"
	"sort"
)

// Approach 1:
// Sort first in asc order.
// Then we know that for each index i, 
// there are at least n-i papers with at least
// array[i] references. Iterate backwards
// once to find the max val
// O(nlog(n) + n) time, O(1) space
func hIndex(citations []int) int {

  sort.Ints(citations) // asc
  
	result, l := 0, len(citations)
	for i := l - 1; i >= 0; i-- {
		count := l - i
		index := min(citations[i], count)
		result = max(result, index)
	}

	return result
}

// Approach 2: straight binary search
// IDEA: The min and max possible H index is
// 0 and the length of the array, respectively.
// We can guess-and-check by doing a binary search
// within the range of 0:n.
// O(nlog(n)) time, O(1) space
func hIndex2(citations []int) int {
	l, r := 0, len(citations)
	result := 0

	for l <= r {
		mid := (l + r) / 2
		if possible(mid, citations) {
			result = max(result, mid)
			l = mid + 1
		} else {
			r = mid - 1
		}
	}

	return result
}

// Returns true if the H index is at least target
func possible(target int, citations []int) bool {
	count := 0
	for _, c := range citations {
		if c >= target {
			count++
		}
	}
	return count >= target
}

// Apprach 3: Given that the H index is bounded by
// the length of the array, we can use an array of
// length n to do a counting sort. For each index i,
// set storage[i] = the number of papers that have
// at least i citations
// O(n) time and O(n) space
func hIndex3(citations []int) int {

	maxIndex := len(citations)
	counts := make([]int, maxIndex+1)

	for _, c := range citations {
		if c > maxIndex {
			counts[maxIndex]++
		} else {
			counts[c]++
		}
	}

	result, papers := 0, 0
	for cites := maxIndex; cites >= 0; cites-- {
		papers += counts[cites]
		index := min(papers, cites)
		result = max(result, index)
	}

	return result
}


// Helpers
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}