Find Kth largest element in an array

# TC : avg O(N) worst O(N^2)
# SC : O(log N) worst O(N)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickselect(left, right):

            # random selection of pivot and move to right
            pidx = random.randint(left, right)
            pivot = nums[pidx]
            nums[pidx], nums[right] = nums[right], nums[pidx]

            # p to track where the next larger element should go
            p, pivot = left, nums[right]
            for i in range(left, right):
                # notice i always moves faster than p
                if nums[i] >= pivot:
                    nums[i], nums[p] = nums[p], nums[i]
                    p += 1

            nums[p], nums[right] = nums[right], nums[p]

            if k < (p + 1):
                return quickselect(left, p-1)
            elif k > (p + 1):
                return quickselect(p+1, right)
            else:
                return nums[p]

        return quickselect(0, len(nums)-1)

# TC : avg O(N) worst O(N^2)
# SC : O(log N) worst O(N)
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        def quickselect(left, right):

            # random selection of pivot and move to right
            pidx = random.randint(left, right)
            pivot = nums[pidx]
            nums[pidx], nums[right] = nums[right], nums[pidx]

            # p to track where the next larger element should go
            p, pivot = left, nums[right]
            for i in range(left, right):
                # notice i always moves faster than p
                if nums[i] <= pivot:
                    nums[i], nums[p] = nums[p], nums[i]
                    p += 1

            nums[p], nums[right] = nums[right], nums[p]

            if k < (p + 1):
                return quickselect(left, p-1)
            elif k > (p + 1):
                return quickselect(p+1, right)
            else:
                return nums[p]

        k = len(nums) - k + 1
        return quickselect(0, len(nums)-1)