leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

kth-largest-element-in-an-arrayV2.py (1698B)

      1 # Intuition:
      2 # Quick Select
      3 
      4 # Approach:
      5 # 1) define pivot
      6 # a) for each value <= pivot_val:
      7 # place in array
      8 # move remaining p values to end
      9 # replace pointer value with new p_val
     10 
     11 # Time Complexity
     12 # WCTC : O(n^2)
     13 # ACTC : O(n)
     14 
     15 # Space Complexity
     16 
     17 # NOTE:
     18 
     19 # They added a worst case test case which results in a TLE
     20 # when using the quick select approach. What a bunch of jerks.
     21 
     22 # Code:
     23 
     24 import random
     25 import heapq
     26 
     27 
     28 class Solution:
     29     def findKthLargest(self, nums: List[int], k: int) -> int:
     30 
     31         if k > 50000 - 1:
     32             nums = [-num for num in nums]
     33             heapq.heapify(nums)
     34             return heapq.nsmallest(k, nums)[-1] * -1
     35 
     36         return self.quickselect(nums, k, 0, len(nums) - 1)
     37 
     38     def quickselect(self, nums, k, lower, upper):
     39         if lower == upper:
     40             return nums[lower]
     41 
     42         pivot = random.randint(lower, upper)
     43         temp = nums[upper]
     44         nums[upper] = nums[pivot]
     45         nums[pivot] = temp
     46         pivot_val = nums[upper]
     47 
     48         filled_to = lower
     49 
     50         for i in range(lower, upper):
     51             if nums[i] < pivot_val:
     52                 temp = nums[filled_to]
     53                 nums[filled_to] = nums[i]
     54                 nums[i] = temp
     55                 filled_to += 1
     56             else:
     57                 continue
     58 
     59         temp = nums[filled_to]
     60         nums[filled_to] = nums[upper]
     61         nums[upper] = temp
     62 
     63         index_of_pivot = filled_to
     64 
     65         if len(nums) - k == index_of_pivot:
     66             return nums[index_of_pivot]
     67         elif len(nums) - k > index_of_pivot:
     68             return self.quickselect(nums, k, index_of_pivot + 1, upper)
     69         else:
     70             return self.quickselect(nums, k, lower, index_of_pivot - 1)