Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 215 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 215 # by problem number
lcpy gen -s kth_largest_element_in_an_array # by problem name
nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
class Solution:
# Time: O(n) average, O(n^2) worst
# Space: O(1)
def find_kth_largest(self, nums: list[int], k: int) -> int:
target_index = len(nums) - k
def quickselect(left: int, right: int) -> int:
pivot = nums[right]
store = left
for i in range(left, right):
if nums[i] <= pivot:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[right] = nums[right], nums[store]
if store == target_index:
return nums[store]
if store < target_index:
return quickselect(store + 1, right)
return quickselect(left, store - 1)
return quickselect(0, len(nums) - 1)
| Time | Space |
|---|---|
| O(n) average, O(n^2) worst | O(1) |