LC 0215 [M] Kth Largest Element in an Array - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=MZaf_9IZCrc&ab_channel=KCAng

quickselect with T = n - k: O(n) average-case

if want kth smallest, then T = k - 1 or partition with A[j] >= pivot

---

class Solution:
    def findKthLargest(self, A: List[int], k: int) -> int:  
        def partition(l, r):
            pivot = A[r]
            i = l

            for j in range(l, r):
                if A[j] <= pivot:
                    A[i], A[j] = A[j], A[i] # swap ij
                    i += 1 # inc i pointer

            A[i], A[r] = A[r], A[i] # swap ir, outside of the for loop
            return i
        
        shuffle(A)

        # looks just like binary search except the median and found case
        N = len(A)
        T = N - k
        
        l = 0
        r = N - 1
        while l <= r:
            p = partition(l, r)
            if p == T:
                return A[p]
            elif p < T:
                l = p + 1
            elif p > T:
                r = p - 1
        return -1

VISUALIZE

def partition(A, l, r):
  pivot = A[r]
  i = l
  print(A)
  for j in range(l, r):
    if A[j] <= pivot:
      print(A, "swap " + "i=" + str(i) + " " + str(A[i]) + ", j=" + str(j) + " " + str(A[j]))
      A[i], A[j] = A[j], A[i]
      i += 1
  print(A, "swap " + "i=" + str(i) + " " + str(A[i]) + ", r=" + str(r) + " " + str(A[r]))
  A[i], A[r] = A[r], A[i]
  print(A)
  return i

arr = [5,2,6,3,1,4]
print(partition(arr, 0, len(arr)-1))

very similar to binary search + lomuto's partition

quickselect: https://www.youtube.com/watch?v=hGK_5n81drs

'''
heap build O(n)
pop: O(klogn)

O(n) + O(klogn)

but it does more work than we need and we might have may as well sorted most of the values by the time we get the answer
'''
'''
partition

is more efficient than heap because it cuts the search space in half

worst case is O(n^2) if we keep choosing the worst pivot every time, but unlikely
so it's about cutting the search space in half each time:
T(n) = T(n/2) + (n-1) = asymptotic(2n) linear
n     1(n-1)
n/2   1(n/2-1)
n/4   1(n/4-1)
n/8   1(n/8-1)
n/16  1(n/16-1)
...   n/2^i-1
0     so depth of this tree is log(n) until we get to 0
2(n-1) - lg(n) = 2(n-1) = 2n = asymptotic(n)


if this were sorted, n - k would us the index of the kth largest item
so we can use this idea with quickselect
'''

class Solution(object):
  def findKthLargest(self, A, k):
    n = len(A)
    l = 0
    r = n - 1

    while l <= r:
      p = self.partition(A, l, r)
      t = n - k
      if p == t:
        return A[p]
      elif p < t:
        # undershot - throw out left and use right
        l = p + 1
      elif p > t:
        # overshot - throw out right and use left
        r = p - 1

    return -1

  # lomuto's partition
  def partition(self, A, l, r):
    pivot = A[r]
    i = l # index of smaller number, the temp var for swapping
    for j in range(l, r):
      if A[j] <= pivot: # if current element is smaller than or equal to pivot (for Kth Smallest Number just flip to >=)
        A[i], A[j] = A[j], A[i] # swap
        i += 1 # increment the smaller number
    # i keeps the furthest we got, r keeps the pivot
    # so when these swap, we make a sandwich: less < pivot < more
    # and now the pivot is in it's final position as if it were sorted for use with n - k
    A[i], A[r] = A[r], A[i]
    # so if the the pivot r which is now at i is less than n - k
    # we know that the answer must be to the right of i
    return i

print(Solution().findKthLargest([5,7,2,3,4,1,6], 3))
# 5