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

Tags: , , , , ,

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