Kth Largest Element in an Array - LeetCode Question

Question

I have been trying to solve Kth Largest Element in an Array

This is my code:

public static int findKthLargest(int[] nums, int k) {
       Queue<Integer> q = new LinkedList<>();
       int max = Integer.MIN_VALUE;

       for(int i=0; i< nums.length; i++){
           if(nums[i]>=max){
               max = nums[i];
               if(q.size() <k)
                   q.add(max);
               else{
                   q.poll();
                   q.add(max);
               }
           }
       }
       return q.peek();
   }

The main idea behind my code is that I keep storing the maximum values in a queue of length K, and after I iterate over all the values in the array I return the first Item as it's the maximium Kth element.

But it fails on the following testcase: Input: Array = [2, 1] K = 2 -- Expected output: 1 -- My Output: 2

I just don't get it, how is 1 is supposed to be the 2nd largest element in the array? Please correct me if I'm messing anything.

Well, in [2,1] the largest value is 2 and the second largest is 1. Why do you think 2 should be the second largest? — Thomas, Oct 14 '19 at 12:09
Checking her output, my guess is she framed her question wrong? — Madstuffs, Oct 14 '19 at 12:11
Btw, your code doesn't make much sense. You're adding new elements as they come until your "queue" has reached a size of `k`. Then you're removing elements from the front if you find larger ones but that's wrong. You'd need to remove the smallest element instead which might be anywhere in that list. — Thomas, Oct 14 '19 at 12:12
You'll only enter your if loop once. So you're queue will also only contain 1 element (value 2). You're logic is indeed a bit off I'm afraid. — TheWhiteRabbit, Oct 14 '19 at 12:13
You have an array sorted in decrease order (like 5,4,2,1). You get the second entry in the array (the second largest) ([5,4,2,1].get(1) is 4). If there is only two elements in an array (like [2,1]) then the second largets is also the smallest one. Which step in this sequence is unclear? — lotor, Oct 14 '19 at 12:13
The easiest way to get what you want would be to sort the array in descending order and returning the element at index k-1. That would probably not be the fastest variant though otherwise that leetcode task wouldn't be a challenge :) — Thomas, Oct 14 '19 at 12:15
Here is an answer of this problem https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on — User_67128, Oct 14 '19 at 12:27

score 3 · Accepted Answer · answered Oct 14 '19 at 12:13

I just don't get it, how is 1 is supposed to be the 2nd largest element in the array?

If the array consists of just two elements - 1 and 2, then 2 is the largest, and 1 is the second-largest. It's also the smallest one, but that's unrelated to the question.

You need to think of a better solution to the problem. The current algorithm only inserts into the queue only if you encounter a new "max" element. But what if the first element you get is the biggest one? You'd only enter it into the queue and miss all the others.

Also, why use a queue? Perhaps an ordered collection would be more useful here?

Kth Largest Element in an Array - LeetCode Question

1 Answers1