Geek's Dream: We Want Kth Element

Kth Largest(smallest) Element Problems

Finding the largest or smallest element in a data structure may be trivial. But how about finding the Kth element? Some times we can even do better than O(N) depending on the data structure given to us.
Here are 3 interesting examples that about finding the Kth element.

Example 1: 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.

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.

-----------------------------------------------------------------------------------------------------------------------

Analyze: There are lot of approaches to this problem. So go head and come up one by yourself !

1. The Simplest one will be sort the array and access the Kth largest element by its index.

--> This approach uses O(n*log(n)) running time and O(1) memory.

2. The second approach will be maintaining a Min Priority Queue that have size K.

--> this approach will run in O(n* log(k)) time and use O(k) memory.

3. The optimal solution will be the one using quick select algorithm, which is very similar to partition method in quick sort.

--> This approach runs in average O(n) time and no extra memory cost.

*Note: There is also a improvement for quickSelect that can make sure we run in O(n) time. We could shuffle the input array to avoid the case that it is sorted in reverse order. Here is the code after add shuffle improvement.

Example 2: Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

-----------------------------------------------------------------------------------------------------------------------

Analyze: if you noticed that we are given a BST and make full use of its property, you may come up with a very elegant solution !

So the idea is by counting how many node is in this current node's left subtree, we can figure out how many node's value in this tree is smallest than current node's value.

Notice that the countNum method is very similar to the Height method in BST.

Example 3: Kth largest element in a stream

Given an infinite stream of integers, find the k’th largest element at any point of time.

Example:

Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3

Output:    {_,   _, 10, 11, 20, 40, 50,  50, ...}

Extra space allowed is O(k).

-----------------------------------------------------------------------------------------------------------------------

Analyze: A solution will be keep a array of size k in sorted order, but the running time for insert a new number will be O(k).

The most efficient way to solve this problem is to maintain a Min Heap of size K, which will let us find the Kth largest in O(1) time and O(logk) time to process a new number.

Here is the code for building and updating a Min Heap in JAVA: