Kth Largest Element – Python 3 (Week 18 – 12)

class Solution:
    """
    @param n: An integer
    @param nums: An array
    @return: the Kth largest element
    """
    def kthLargestElement(self, k, A):
        # write your code here
        if not A or k < 1 or k > len(A):
            return None
        return self.partition(A, 0, len(A) - 1, len(A) - k)
        
    def partition(self, A, start, end, k):
        
        if start == end:
            return A[k]
            
        left, right = start, end
        pivot = A[(start + end) // 2]
        
        while left <= right:
            while left <= right and A[left] < pivot:
                left += 1
            while left <= right and A[right] > pivot:
                right -= 1
            if left <= right:
                A[left], A[right] = A[right], A[left]
                left += 1
                right -= 1
            
        if k <= right:
            self.partition(A, start, right, k)
        if k >= left:
            self.partition(A, left, end, k)
            
        return A[k]