CODEWITHSUNDEEP
pythonrecursion
Radk7
Radk7

Reputation: 43

Finding the Kth Largest element in a Python List using recursion

Given an input list that contains some random unsorted numbers, I am trying to write a program that outputs the kth largest distinct element in that list. For example:

Input: 
el = [10,10, 20,30,40, 40]
k = 2
Output: 30 #Since 30 is the second largest distinct element in the list

The following function, takes as input a list, the pivot Index and k and populates list "lesser" with all elements lesser than the pivot and populates another list "greater" with all elements greater than the pivot.

Now, looking at the length of the two list, I can determine if the kth largest element is in the lesser list or the greater list. Now I recursively call the same function. However, my program's output is wrong for certain values of k.

def kthLargest(el, pivotIndex, k):
    pivot = el[pivotIndex]
    lesser = [] #List to store all elements lesser than pivot
    greater = [] #Lsit to store all elements greater than pivot
    equals = [] #List to store all elements equal to pivot

    for x in el:
        if x > pivot:
            greater.append(x)
        elif x < pivot:
            lesser.append(x)
        else:
            equals.append(x)
    g = len(greater) #Length of greater list
    l = len(lesser) 

    if(g == k - 1): #If greater list has k-1 elements, that makes the pivot kth largest element
        return pivot
    elif(g < k):
        return kthLargest(lesser, l - 1, k) #If greater list is smaller than k, kth largest element is in lesser list
    else:
        return kthLargest(greater,  g - 1, k) #Else kth largest element is in greater list

Upvotes: 4

Views: 12935

Answers (7)

soumya-kole
soumya-kole

Reputation: 1365

On top of S Rohith Kumar's answer, If the input has duplicate values, then the answer can be :

print(sorted(set(lst),reverse=True)[k-1])

Upvotes: 0

S Rohith Kumar
S Rohith Kumar

Reputation: 11

My way of finding the Kth largest element is...

lst=[6,2,3,4,1,5]
print(sorted(lst,reverse=True)[k-1])

Upvotes: 1

user1464878
user1464878

Reputation:

Algorithm: Take the index of max value and convert to zero.

def high(arr,n):
    for i in range(n+ 1 ):
        arr[arr.index(max(arr))] = 0
        return max(arr)
high([1,2,3,4,5], 2)

Upvotes: 0

Rama Tripathy
Rama Tripathy

Reputation: 11

Here is a simple solution: 

def kthmax(k, list):
    if (k == 1):
        return max(list)
    else:
        m = max(list)
        return(kthmax(k-1, [x for x in list if x != m]))

kthmax(3,[4, 6, 2, 7, 3, 2, 6, 6])

Output: 4

Upvotes: 1

Vinord Anand
Vinord Anand

Reputation: 21

If we can pass in a list or series that is already sorted in descending order, e.g 

el.sort_values(ascending=False, inplace = True)

then you can easily find the kth largest (index,value) tuple using just simple slicing of sorted dataframe column and/or list

def kth_largest(input_series, k):
    new_series = input_series[k-1:len(input_series)]
    return (np.argmax(new_series) , np.max(new_series))

el = pd.Series([10, 10, 53, 20, 30, 40, 59, 40])
print el
k = 2

el.sort_values(ascending=False, inplace=True)

print kth_largest(el, 2)

Output: 30
0    10
1    10
2    53
3    20
4    30
5    40
6    59
7    40
dtype: int64
(2, 53)

Upvotes: 0

Nick Becker
Nick Becker

Reputation: 4214

Is there any reason you want to use recursion? To find the kth largest element of a list you have to look through the entire list, so the problem is essentially O(n) complexity anyway.

You could do this without recursion like this:

el = [10, 10, 53, 20, 30, 40, 59, 40]
k = 2

def kth_largest(input_list, k):
    # initialize the top_k list to first k elements and sort descending
    top_k = input_list[0:k]
    top_k.sort(reverse = True)

    for i in input_list[k:]:
        if i > top_k[-1]:
            top_k.pop() # remove the lowest of the top k elements
            top_k.append(i) # add the new element
            top_k.sort(reverse = True) # re-sort the list

    return top_k[-1] # return the kth largest


kth_largest(el, k)

Upvotes: 1

Checkmate
Checkmate

Reputation: 1154

There's an easy way to do this problem using recursion. I'm just not sure why you need the pivot in the problem description... For example:

def find_kth(k, arr):
    if k == 1:
        return max(arr)
    m = max(arr)
    new_arr = list(filter(lambda a: a != m, arr))
    return(find_kth(k-1, new_arr))

Upvotes: 0

Related Questions