Find the H-Index

Problem

You’re given an array [1,3,5,0,6,5,7] of non-negative integers. Return the h-index of this array, which is the largest number with at least that many elements. In this case, there are 3 elements >= 3 and 2 elements >= 4, so the H-index is 3.

Thought Process

First, let’s think. What’s the largest possible h-index? 5, because there are 5 elements in the list. What’s the lowest possible h-index? 0, because all elements are non-negative.

What if we sorted the array?

If the array is sorted, it’s easy to see how many elements are greater than or equal to it.

Let’s go through the array now.

[0, 1, 3, 5, 6, 6, 7]

There are 7 elements greater than or equal to 0.

There are 6 elements greater than or equal to 1.

There are 5 elements greater than or equal to 3.

There are 4 elements greater than or equal to 5.

XXXXXXXXXXX

We terminate our algorithm. We have 4 elements greater than or equal to 5. The last number that worked was 3, but we have a little bit more information. If we know 4 elements are >= 5, then 4 elements are also >= 4, so we have our answer. 4

Code

def determine(array):
    array = sorted(array)# sort the array
    if array == []: #Edge case
        return 0
    length = len(array)
    for index,element in enumerate(array):
        if element >= length - index:
            return length - index
    return 0
     

Can we do better?

This runs in O(n log n) time because we have to sort the array. For an unsorted array, we must use all n data points in the array, so there’s no way we can do it in less than O(n) time.

Therefore, let’s try to do it in O(n) time. If we can, then we have the best solution.

Thought process

Given a list like [6, 1, 7, 0, 3, 5, 6], we can do a “waterfall”.

We start with a list like this

greaterThan[0] = 0, greaterThan[1] = 0, … greaterThan[7 (length of our array)] = 0

As we iterate through, we add to the elements we see. For example, we go through the array, and we see a 6, so we know there’s at least one element greater than or equal to 6. So, greaterThan[6] += 1.

In the end, we have this: greaterThan = [1, 1, 0, 1, 0, 1, 2, 1]. However, it’s like a waterfall. The number of elements greater than or equal to 6 equals the number of elements = 6 + the number of elements greater than or equal to 7.

[1, 1, 0, 1, 0, 1, 2, 1] becomes
[7, 6, 5, 5, 4, 4, 3, 1]. Now, we do pretty much the same thing as before.

There are 7 elements greater than 0.
There are 6 elements ≥ 1
There are 5 elements ≥ 2
There are 5 elements ≥ 3
There are 4 elements ≥ 4. We’re done now.

Faster than that, we can see

There is 1 element ≥ 7.
There are 3 elements ≥ 6.
There are 4 elements ≥ 5.
There are 4 elements ≥ 4.

Code

def determine(array):
    if array == []: #Edge case
        return 0
    greaterThan = [0 for i in range(len(array) + 1)]
    for i in array:
        greaterThan[min(len(array), i)] += 1
    
    #waterfall
    if greaterThan[-1] >= len(array):
        return len(array)
    for i in range(len(array) - 1, -1, -1):
        greaterThan[i] += greaterThan[i+1]
        if greaterThan[i] >= i:
            return i