> For the complete documentation index, see [llms.txt](https://jaywin.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://jaywin.gitbook.io/leetcode/solutions/0215-kth-largest-element-in-an-array.md).

# 0215. Kth Largest Element in an Array

<https://leetcode.com/problems/kth-largest-element-in-an-array>

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

**Example 2:**

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

**Constraints:**

* `1 <= k <= nums.length <= 104`
* `-104 <= nums[i] <= 104`

## ac1: quick select

Iterative version:

```java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Edge cases: invalid input.

        k--; // Kth largest, index = k - 1 in sorted array.
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int p = getArrayPartitionIndex(nums, start, end);
            if (p == k) return nums[p];

            if (p < k) {
                start = p + 1;
            } else if (p > k) {
                end = p - 1;
            }
        }

        return -1;
    }

    private int getArrayPartitionIndex(int[] nums, int start, int end) {
        int pivot = nums[end];
        int left = start;
        for (int right = start; right < end; right++) {
            if (nums[right] >= pivot) {
                swap(nums, left, right);
                left++;
            }
        }
        swap(nums, left, end);
        return left;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
```

Recursive versioned:

```java
// quick select: set pivot, opposite direction two pointers

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // sort, nlogn
        // partition, quick select
        // pivot, left/right

        // edge cases
        if (nums.length < 1) return -1;

        return quickSelect(nums, 0, nums.length-1, k);
    }
    private int quickSelect(int[] nums, int s, int e, int k) {
        // exit
        if (s == e) return nums[s];

        // init
        int l = s, r = e, pivot = nums[(s+e)/2];

        // loop
        while (l <= r) {
            while(l<=r && nums[l] > pivot) l++; // cannot put '==' here, will pass then entire list, cause stackoverfloww
            while (l <= r && nums[r] < pivot) r--;
            if (l <= r) {
                if (l < r) swap(nums, l, r);
                l++;
                r--;
            }
        }

        // determine which part contains kth
        if (s + k - 1 <= r) return quickSelect(nums, s, r, k);
        if (s + k - 1 >= l) return quickSelect(nums, l, e, k-(l-s)); //  be careful set new value for k by k-(l-s)
        return nums[r+1]; // when there is value in the middle, right, kth, left
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

// Time: O(n)
```

## ac2: priority queue

O(NlogK)