CODEWITHSUNDEEP
javaqueue
Basma M. Mostafa
Basma M. Mostafa

Reputation: 47

Kth Largest Element in an Array - LeetCode 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.

Upvotes: 0

Views: 820

Answers (1)

Malt
Malt

Reputation: 30285

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?

Upvotes: 3

Related Questions