leetcode

commit 3a65a9dbdfc3c1a39189d0e3b3f89153f3e6de8f
parent 728eede3fb86c5359705e1581c57d98095bbfdb6
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  7 Jul 2025 14:51:36 -0500

Completed kth largest element in an array

Diffstat:
A
kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV2.py
 | 
70
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 70 insertions(+), 0 deletions(-)
diff --git a/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV2.py b/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV2.py
@@ -0,0 +1,70 @@
+# Intuition:
+# Quick Select
+
+# Approach:
+# 1) define pivot
+# a) for each value <= pivot_val:
+# place in array
+# move remaining p values to end
+# replace pointer value with new p_val
+
+# Time Complexity
+# WCTC : O(n^2)
+# ACTC : O(n)
+
+# Space Complexity
+
+# NOTE:
+
+# They added a worst case test case which results in a TLE
+# when using the quick select approach. What a bunch of jerks.
+
+# Code:
+
+import random
+import heapq
+
+
+class Solution:
+    def findKthLargest(self, nums: List[int], k: int) -> int:
+
+        if k > 50000 - 1:
+            nums = [-num for num in nums]
+            heapq.heapify(nums)
+            return heapq.nsmallest(k, nums)[-1] * -1
+
+        return self.quickselect(nums, k, 0, len(nums) - 1)
+
+    def quickselect(self, nums, k, lower, upper):
+        if lower == upper:
+            return nums[lower]
+
+        pivot = random.randint(lower, upper)
+        temp = nums[upper]
+        nums[upper] = nums[pivot]
+        nums[pivot] = temp
+        pivot_val = nums[upper]
+
+        filled_to = lower
+
+        for i in range(lower, upper):
+            if nums[i] < pivot_val:
+                temp = nums[filled_to]
+                nums[filled_to] = nums[i]
+                nums[i] = temp
+                filled_to += 1
+            else:
+                continue
+
+        temp = nums[filled_to]
+        nums[filled_to] = nums[upper]
+        nums[upper] = temp
+
+        index_of_pivot = filled_to
+
+        if len(nums) - k == index_of_pivot:
+            return nums[index_of_pivot]
+        elif len(nums) - k > index_of_pivot:
+            return self.quickselect(nums, k, index_of_pivot + 1, upper)
+        else:
+            return self.quickselect(nums, k, lower, index_of_pivot - 1)