> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Kth Largest Element in an Array

> Tested Python solution for LeetCode 215 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 215, Medium. Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect. [View on LeetCode](https://leetcode.com/problems/kth-largest-element-in-an-array/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 215   # by problem number
lcpy gen -s kth_largest_element_in_an_array   # by problem name
```

## Problem

Given an integer array `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?

### Examples

```
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
```

### Constraints

* 1 \<= k \<= nums.length \<= 10^5
* -10^4 \<= nums\[i] \<= 10^4

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/kth_largest_element_in_an_array/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/kth_largest_element_in_an_array/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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)
```

## Complexity

| Time                       | Space |
| -------------------------- | ----- |
| O(n) average, O(n^2) worst | O(1)  |

## Tags

[Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).