[Top Interview 150] 274. H-Index

Solution)

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # Initialization
        space = []

        for i in range(len(citations)):
            # Fill empty space
            if not space:
                if citations[i] > 0:
                    space.append(citations[i])
            
            else:
                # If cur elem is bigger than cur h-index
                if citations[i] > len(space):
                    space.append(citations[i])

                    # If the smallest elem is smaller than updated h-index
                    if min(space) < len(space):
                        space.remove(min(space))

        return len(space)

 
 
Problem: LeetCode
 
Time Complexity: O(n)?
Space Complexity: O(n)
* Please let me know if this solution costs more than O(n)...

Explanation)

Obviously, the easiest approach is to reverse-sort citations and increment the count as you iterate through that sorted citations.
 
However, I didn't want to use that approach as that not only costs O(n log n) time complexity but also is just boring. Thus, I decided to spend two hours staring at the code and came up with (hopefully) faster solution using an extra memory.
 
Basically, I have an extra space where I'm going to append elements of citations that only goes under the conditions of h-index. I'll go on to the details in specific steps.
 
 

Initialization)

We'll save suitable elements of citations in a variable space.
 
For example,
if space is [] and the current element is 1, we'll add 1 to space, because 1 is bigger than a current h-index (which is 0)
if space is [3] and the current element is 2, we'll add 2 to space, because 2 is bigger than a current h-index (which is 1)
 

def hIndex(self, citations: List[int]) -> int:
        space = []

 
 

When space is empty)

Since we initialized space as an empty list, we first have to add an element to space.
 
If space is empty, check if the current element is greater than zero. Adding zero to space has no meaning as it means that paper has not been cited, thus it'll have no effect on h-index.
 
So we'll only add elements that are greater than zero.
 

def hIndex(self, citations: List[int]) -> int:
        space = []

        for i in range(len(citations)):
            if not space:
                if citations[i] > 0:
                    space.append(citations[i])

 
 

Once space is not empty)

After space is occupied, we'll add elements according to h-index.
 
Current length of space is a current h-index. If the current element is greater than the current h-index, it means we can append one more paper to space and increment h-index.
 
Thus, if the current element is greater than the current h-index, we'll append that element to space.  
 

def hIndex(self, citations: List[int]) -> int:
        space = []

        for i in range(len(citations)):
            if not space:
                # Fill empty space
            
            else:
                if citations[i] > len(space):
                    space.append(citations[i])

 
 

Edge Case)

After we added the current element to space, we now have to check an edge case.
 
Say space is [2, 9] and the current element is 7.
Since 7 is greater than 2 (current h-index), we'll append 7 to space resulting [2, 9, 7].
However, now h-index is 3, but 2 in space doesn't meet that condition of h-index. Thus, we have to remove 2 from space. 
 
This is the edgcase. After we add a new element we have to check if the minimum element in space is still greater than or equal to the new h-index.
 
If the min element is less than h-index, we'll remove that element from space.
 
After the iteration of citations is completed, we'll return length of space which is the maximum h-index.
 

def hIndex(self, citations: List[int]) -> int:
        space = []

        for i in range(len(citations)):
            if not space:
                # Fill empty space
            
            else:
                if citations[i] > len(space):
                    # append cur elem

                    if min(space) < len(space):
                        space.remove(min(space))

        return len(space)

 
 
 
I was trying my best to find a faster solution than the typical sorting method, which took me a while to finish this problem. Even though this might not be an optimal solution, I'm still happy that I solved this without looking at other solutions.