# java - without - kth smallest element in an array in c

## Java, Finding Kth largest value from the array (4)

Edit: Check this answer for O(n) solution.

You can probably make use of PriorityQueue as well to solve this problem:

``````public int findKthLargest(int[] nums, int k) {
int p = 0;
int numElements = nums.length;
// create priority queue where all the elements of nums will be stored
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

// place all the elements of the array to this priority queue
for (int n : nums){
}

// extract the kth largest element
while (numElements-k+1 > 0){
p = pq.poll();
k++;
}

return p;
}
``````

From the Java doc:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (`offer`, `poll`, `remove()` and `add`); linear time for the `remove(Object)` and `contains(Object)` methods; and constant time for the retrieval methods (`peek`, `element`, and `size`).

The for loop runs `n` times and the complexity of the above algorithm is `O(nlogn)`.

Suppose you have an unordered array with N distinct values

\$input = [3,6,2,8,9,4,5]

Implement a function that finds the Kth largest value.

EG: If K = 0, return 9. If K = 1, return 8.

``````private static int getMax(Integer[] input, int k)
{
List<Integer> list = Arrays.asList(input);
Set<Integer> set = new TreeSet<Integer>(list);

list = new ArrayList<Integer>(set);
int value = (list.size() - 1) - k;

return list.get(value);
}
``````

I just tested and the method works fine based on the question. However, interviewee said, `in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case?` As hint, he suggested to use `min heap`. Based on my knowledge each child value of heap should not be more than root value. So, in this case if we assume that 3 is root then 6 is its child and its value is grater than root's value. I'm probably wrong but what you think and what is its implementation based on `min heap`?

He has actually given you the whole answer. Not just a hint.

And your understanding is based on `max heap`. Not `min heap`. And it's workings are self-explanatory.

In a min heap, the root has the minimum (less than it's children) value.

So, what you need is, iterate over the array and populate `K` elements in min heap. Once, it's done, the heap automatically contains the lowest at the root.

Now, for each (next) element you read from the array, -> check if the value is greater than root of min heap. -> If yes, remove root from min heap, and add the value to it.

After you traverse your whole array, the root of min heap will automtically contain the `k`th largest element.

And all other elements (k-1 elements to be precise) in the heap will be larger than `k`.

Here is the implementation of the Min Heap using PriorityQueue in java. Complexity: `n * log k`.

``````import java.util.PriorityQueue;

public class LargestK {

private static Integer largestK(Integer array[], int k) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
int i = 0;
while (i<=k) {
i++;
}
for (; i<array.length; i++) {
Integer value = queue.peek();
if (array[i] > value) {
queue.poll();
}
}
return queue.peek();
}

public static void main(String[] args) {
Integer array[] = new Integer[] {3,6,2,8,9,4,5};
System.out.println(largestK(array, 3));
}
}
``````

Output: 5

The code loop over the array which is `O(n)`. Size of the PriorityQueue (Min Heap) is k, so any operation would be `log k`. In the worst case scenario, in which all the number are sorted ASC, complexity is `n*log k`, because for each element you need to remove top of the heap and insert new element.

One approach for constant values of `k` is to use a partial insertion sort.

(This assumes distinct values, but can easily be altered to work with duplicates as well)

``````last_min = -inf
output = []
for i in (0..k)
min = +inf
for value in input_array
if value < min and value > last_min
min = value
output[i] = min
print output[k-1]
``````

(That's pseudo code, but should be easy enough to implement in Java).

The overall complexity is `O(n*k)`, which means it works pretty well if and only if `k` is constant or known to be less that `log(n)`.

On the plus side, it is a really simple solution. On the minus side, it is not as efficient as the heap solution