> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/search/215kth-largest-element-in-an-array.md).

# 215\_Kth Largest Element in an Array

Find the **k**th largest element in an unsorted array. There might be duplicates in the array.

**Example 1:**

```
Input:[3,2,1,5,6,4] and k = 2
Output: 5
```

**Example 2:**

```
Input:[3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
```

## Solution 1:

**Idea**:

* Sort the array in descending order, then get the kth element.

**Time Complexity**: $$O(n \log{n})$$

**Space Complexity**: $$O(1)$$

```python
def findKthLargest(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    nums.sort(reverse=True)
    return nums[k-1]
```

## Solution 2: ??

**Idea**:

* store a candidate set of k elements in a min-heap

**Time Complexity**: $$O(n \log{k})$$

**Space Complexity**: $$O(k)$$

## Solution 3

**Idea**:

* Similar to quick sort
* Randomly choose a pivot, store the elements less than the pivot,  larger than the pivot and the number of duplicated pivot n.
* If including some or all the pivot, the elements larger than (or equal to) the pivot can be k, then the pivot is the kth largest.
* If less than k, the values in the larger group and pivot are not enough for kth largest, so we focus on the array with smaller values and find the next several largest.
* If larger than k, focus on the larger group for the kth largest element.

**Time Complexity**: $$O(n \log{n})$$

**Space Complexity**: $$O(n)$$ we can reduce the extra space to $$O(1)$$by in-place partition around the pivot.

```python
def findKthLargest(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    if not nums: return False
    if len(nums) < k: return False

    import random
    index = random.randint(0, len(nums)-1)
    pivot = nums[index]

    # partition the array around the pivot
    nums_smaller = []
    nums_larger = []
    n = 0   # number of pivot duplicates
    for i in range(len(nums)):
        if nums[i] > pivot:
            nums_larger.append(nums[i])
        elif nums[i] < pivot:
            nums_smaller.append(nums[i])
        else:
            n += 1

    if k-n<= len(nums_larger) <= k-1 :
        return pivot
    elif len(nums_larger) > k-1:
        # focus on the larger part
        return findKthLargest(nums_larger, k)
    else:
        # focus on the smaller part
        return findKthLargest(nums_smaller, k-len(nums_larger)-n)
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/search/215kth-largest-element-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.