< Back





215. Kth Largest Element in an Array

Again, another problem that could be easily solved with a heap, however, we can get a better time
complexity using quickselect. Choosing a random pivot, we sort all numbers less than the pivot into
the right array, and all numbers greater than the pivot into the left array, and all numbers equal to
the pivot into the middle array.

If the length of the left array is greater than or equal to k, we know that our answer is somewhere
in the left array. We recursively call quickselect on the left array.

If the length of the left and middle array combined are less than k, we know that our answer is
somewhere in the right array. We subtract the sizes of the left and middle array from k and
recursively call quickselect on the right array.

If both of these decisions return false, we know our answer is in the middle array, and we return
the pivot.

The solution is as follows:


  class Solution:
      def findKthLargest(self, nums, k):
          def quick_select(nums, k):
              pivot = random.choice(nums)
              left, mid, right = [], [], []

              for num in nums:
                  if num > pivot:
                      left.append(num)
                  elif num < pivot:
                      right.append(num)
                  else:
                      mid.append(num)

              if k <= len(left):
                  return quick_select(left, k)

              if len(left) + len(mid) < k:
                  return quick_select(right, k - len(left) - len(mid))

              return pivot

          return quick_select(nums, k)


_ Time Complexity:

  O(n) - The quickselect time complexity is O(n) on average.

_ Space Complexity:

  O(n) - We have to use space to store the arrays.