from typing import *


class Solution:
    def findPivotIndex(self, nums: List[int]) -> int:
        pivot = nums[0]
        left, right = 0, len(nums) - 1
        while left < right:
            while nums[right] < pivot and left < right:
                right -= 1
            while nums[left] >= pivot and left < right:
                left += 1
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp

        nums[0] = nums[left]
        nums[left] = pivot
        return left

    def findKthLargest(self, nums: List[int], k: int) -> int:
        # if len(nums) == 1 and k == 1:
        #    return nums[0]

        index = self.findPivotIndex(nums)
        if index == k - 1:
            return nums[index]
        elif index > k - 1:
            return self.findKthLargest(nums[:index], k)
        else:
            return self.findKthLargest(nums[index + 1:], k - index - 1)


if __name__=='__main__':
    s = Solution()
    print(s.findKthLargest([3,2,1,5,6,4], 2))
