# Two python solutions

• One O(n) time and O(n) space:

def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
nc = len(citations)
citCounts = (nc+1)*[0]
for n in citations:
if n>=nc:
citCounts[nc] += 1
else:
citCounts[n] += 1
accumC=0
for i in range(nc,-1,-1):
accumC += citCounts[i]
if accumC>=i:
return i
return i

One O(nlgn) time and O(1) space:

def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
def onePartition(loc,citations,s,e):
pivot = citations[loc]
index = s
for i in range(s,e):
cit = citations[i]
if cit>=pivot:
citations[i] = citations[index]
citations[index] = cit
index += 1
citations[loc] = citations[index-1]
citations[index-1] = pivot
return index-1

nc = len(citations)
if not nc: return 0
loc,s,e = 0,1,nc
hindex = 1 if citations[loc]>0 else 0
while(s<=e):
#print 'Before: ',loc,' ',citations
nloc = onePartition(loc,citations,s,e)
if(nloc+1==citations[nloc]):
return max(hindex,nloc+1)
elif(nloc+1>citations[nloc]):
hindex = max(hindex,citations[nloc])
loc,s,e=loc,s,nloc
else:
hindex = max(hindex,nloc+1)
loc,s,e=nloc+1,nloc+2,e
#print 'After: ', nloc,' ',citations,' ',hindex
return hindex

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.