# LeetCode – Find the kth largest element in an unsorted array (Java)

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.

For example,
Given `[3,2,1,5,6,4]` and k = 2, return 5.

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

## Analysis

It’s easy to first sort the array, then pick up the `Kth` largest element. The time complexity is `O(nlogn)` if we use quick sort.

## Min Heap Based Method

A better method is use a min heap or PriorityQueue with size `K`.  We first insert the first K elements of the Array into the heap.

Then, we continue scan the array, if the current value is smaller than the top of the heap, ignore it. Otherwise remove the top of the heap, and insert the current value into the heap. The time complexity is `O(nlogK)`. Space complexity is` O(K)` as there are K elements stored in the heap.

The following is the algorithm based on the Java PriorityOueue, which in default is a min heap.

## Use Quick Sort Partition Algorithm

The third method is based on the idea of quick sort’s partition algorithm. Given a pivot, we partition the array into three parts `ALeft = A[0 .. pivotIndex - 1],  A[pivotIndex], ARight = A[pivotIndex + 1, A.length - 1]`.

We know all the elements in `ALeft` are less than or equal to the pivot value, and all the elements in `ARight` are larger than or equal to the pivot value.

If `pivotIndex` equals to `A.length - K`, pivot is the answer.

If `pivotIndex` is less than `A.length - K`, we know the `Kth` largest element is the `Kth` largest element in `ARight`.

If `pivotIndex` is larger than `A.length - K`, we know the `Kth` largest element is the `K - (A.length - pivotIndex)` th largest element in `ALeft`.

The following is the Java implementation of this method.

Reference: http://algs4.cs.princeton.edu/23quicksort/Quick.java.html