# 215. Kth Largest Element in an Array (Medium)

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

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

## Solutions

``````class Solution {
public int findKthLargest(int[] nums, int k) {
heapSort(nums, k);

return nums[nums.length - k];
}

private void heapSort(int[] nums, int k) {
int len = nums.length;
for (int i = 1; i <= k; i++) {
maxHeapify(nums, len - i);
swap(nums, 0, len - i);
}
}

private void maxHeapify(int[] nums, int n) {

// n is index and pay close attention to the difference of index and length.
// Assume length is 2, the parent slot should be (2 - 1) / 2 = 0,
// otherwise if parent being 1, left = 2, right = 3, both exceed the boundary of nums

for (int i = n / 2; i >= 0; i--) {
// parent node index
int pid = i;

// left child index
int left = pid * 2;

// right child index
int right = pid * 2 + 1;

// no right child node
if (right > n) {
right = left;
}

if (nums[left] > nums[pid]) {
swap(nums, left, pid);
}

if (nums[right] > nums[pid]) {
swap(nums, right, pid);
}
}
}

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