Kth largest element in an array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given[3,2,1,5,6,4]and k = 2, return 5.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Idea: First sorting and then finding is an easier solution. But time complexity would be O(n logn) Idea: Use the partition method of quickSort and then determine the position of the pivotElement. Based on that calculate the new k and either the right or the left side of the array. Keep recursing. In this case time complexity is O(n)

T(n) = O(n) + T(n/2)

n + n/2 + n/4 + =~O(n)

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        #print
        #print 'nums: ', nums
        first = 0
        last = len(nums) - 1

        pivotIndex = self.partition(nums, first, last)
        #print 'pivotIndex = ', pivotIndex, ' pivotElem = ', nums[pivotIndex]
        pivotsLargestPosition = len(nums) - pivotIndex
        #print 'pivotsLargestPosition: ', pivotsLargestPosition, ' k: ', k
        if pivotsLargestPosition == k:
            return nums[pivotIndex]
        elif pivotsLargestPosition < k:
            return self.findKthLargest(nums[:pivotIndex], (k - pivotsLargestPosition))
        else:
            return self.findKthLargest(nums[pivotIndex+1:], (k))


    def partition(self, nums, first, last):
        pivot = nums[first] # choosing the pivot can be randomized
        #print 'pivot chosen: ', pivot, ' index: ', first
        leftPtr = first + 1
        rightPtr = last

        done = False
        while not done:

            while leftPtr <= rightPtr and nums[leftPtr] <= pivot:
                leftPtr += 1
            while rightPtr >= leftPtr and nums[rightPtr] >= pivot:
                rightPtr -= 1

            if rightPtr < leftPtr:
                done = True
            else:
                temp = nums[rightPtr]
                nums[rightPtr] = nums[leftPtr]
                nums[leftPtr] = temp

        temp = nums[rightPtr]
        nums[rightPtr] = nums[first]
        nums[first] = temp

        return rightPtr # location of the pivot