# 215. Kth Largest Element in an Array

## LeetCode [215. Kth Largest Element in an Array](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

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.

**Example 1:**

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

**Constraints:**

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

### Tags

Divide and Conquer, Heap

### Solution

#### Solution 1:

We can perform the partition operation adopted in quick sort algorithm until `pivot == k`.

* `l == r`, return `nums[l]`;
* `pivot == k`, return `nums[k]`;
* `pivot > k`, `partition(left, pivot - 1)`;
* `pivot < k`, `partition(pivot + 1, right)`;

#### Solution 2:

We use heap with capacity of `k`, where the root is the minimum element, to store the top-k largest elements in the given array. We keep pushing elements into the heap until the size of the heap is `k`. Then, we compare the current element with the root of the heap, if the root is smaller, we pop an element from the heap and push the current one into it. Finally, we return the root.

### Complexity

#### Solution 1:

* Time complexity: $$O(n^2)$$, the worst case is we partition the array for `n` times. We can introduce random partition to speed up this up to $$O(n)$$ ;
* Space complexity: $$O(\log(n))$$, for recursion stack.

#### Solution 2:

* Time complexity: $$O(n)$$
* Space complexity: $$O(k)$$

### Code

#### Solution 1 (Quick-sort):

```go
func findKthLargest(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}
	return topK(nums, 0, len(nums)-1, len(nums)-k)
}

func topK(data []int, left, right, k int) int {
	if left == right {
		return data[left]
	}
	pivot := partition(data, left, right)
	if pivot == k {
		return data[pivot]
	}
	if pivot > k {
		return topK(data, left, pivot-1, k)
	}
	return topK(data, pivot+1, right, k)
}

func partition(data []int, left, right int) int {
	pivotElem := data[right]
	i := left - 1
	for j := left; j < right; j++ {
		if data[j] < pivotElem {
			i++
			data[i], data[j] = data[j], data[i]
		}
	}
	i++
	data[i], data[right] = data[right], data[i]
	return i
}
```

#### Solution 2 (Heap):

```go
type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	x := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return x
}

func findKthLargest1(nums []int, k int) int {
	h := make(IntHeap, 0, k)
	for _, num := range nums {
		if len(h) < k {
			heap.Push(&h, num)
		} else if num > h[0] {
			heap.Pop(&h)
			heap.Push(&h, num)
		}
	}
	return h[0]
}
```


---

# Agent Instructions: 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://txfs19260817.gitbook.io/leetcode-go-notes/solutions/215.-kth-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.