I wanted to write code such that I could find the k-th largest number using quick-sort and wrote the following in LeetCode, which LeetCode will call upon findKthLargest first
class Solution(object):
def partition(self, arr,left,right):
piv = arr[right]
i = left-1
counter = left
while (counter<right):
if (arr[counter]<piv):
i = i+1
tmp = arr[counter]
arr[counter]=arr[i]
arr[i]=tmp
counter = counter+1
temp = arr[i+1]
arr[i+1]=arr[right]
print('pivot '+str(piv)+' at '+str(i+1))
arr[right]=temp
print("at the nmoment "+str(arr))
return (i+1)
def helper(self,arr,left,right,k):
if (left>=right):
return
p = self.partition(arr,left,right)
print("p is now "+str(p))
if (p==len(arr)-k):
return int(arr[p])
self.helper(arr,left,p-1,k)
self.helper(arr,p+1,right,k)
def findKthLargest(self, nums, k):
f= self.helper(nums,0,len(nums)-1,k)
print(f)
I've even printed (arr[p]) INSIDE the helper method and it gave me the correct answer however inside of the method findKthLargest the variable f shows up as a none type and I was wondering where did I go wrong? At the moment I believe that it is returning a none type since inside of the recursive loops when checking if (left>=right) inside of the helper method it returns none
The problem is that your helper function does not always return a value. Only in the base case, where the if condition is true, it will return a numeric value. But it should also return that same number where the corresponding recursive calls are made.
So change:
self.helper(arr,left,p-1,k)
self.helper(arr,p+1,right,k)
to:
result = self.helper(arr,left,p-1,k)
if result is not None:
return result
return self.helper(arr,p+1,right,k)
This way the deepest return value will bubble up the recursion tree, and a success in the first recursive call will avoid that the second recursive call is made.