2 Kth Smallest Element

[@naweliverma5484]

Kabhi itne awesome tarike se kisi ne samjahya hi nai. :D

[@NotNotNithin]

In Java, by default, it is a min-heap. Min Heap: PriorityQueue minHeap = new PriorityQueue(); Max Heap: Using comparator to make it a max heap. PriorityQueue maxHeap = new PriorityQueue((a, b) -> b - a); Updated Java code: private static int findKthSmallestElement(int[] arr, int k, int size) { PriorityQueue maxHeap = new PriorityQueue((a, b) -> b - a); for (int i = 0; i < size; i++) { maxHeap.add(arr[i]); if (maxHeap.size() > k) { maxHeap.poll(); } } return maxHeap.peek(); }

[@varshityadav5467]

thanks bhai bacha liya tune idhar udhar bhatakne se

[@56sanjivanisingh58]

thankyou so much

[@pawanmaurya8300]

@@varshityadav5467 I just also came to check this 😅

[@YogeshShinde31]

FYI..Comparator can be Comparator.reverseOrder() for maxheap of Integer.

[@kuchettisantoshkumar65]

PriorityQueue maxHeap = new PriorityQueue(Collections.reverseorder()); This can also be used and very easy to remember for a beginner.

[@Samtoosoon]

Priority -queue

[@Samtoosoon]

Min big

[@shisui_one_eye_guy]

The time complexity of priority_queue to insert one element is O(logk) so inserting "k" element will take O(klogk) and (n-k) element are remaining to insert will take (n-k)logk time so total time complexity is T = klogk + (n-k)logk T = klogk + nlogk -klogk T = nlogk Very Nice, I got it And I liked it , Thank You bhaiya

[@abhinavsharma3819]

I think there is a correction required. worst case time complexity for k elements is k(logn), and for n-k it will be (n-k)log(n) , TOtal will be nLogn, which is the complexity of insertion of full array in a heap. It will be equal to merge-sort only, nothing less

[@shisui_one_eye_guy]

@@abhinavsharma3819 no bro, time complexity of inserting in Priority_queue of size k is logk in worst case so,time comp. inserting n elements in k size is nlogk p_queue

[@shrinathdeva6997]

Well actually the worst case complexity is still nlogn only as in the worst case k = n. Hope you get why the worst case complexity is not nlogk

[@manishkumar-qn6lx]

@Nahrma Bozonda Thanks for such beautiful explanation.

[@utpalpodder-pk6vq]

@@shrinathdeva6997 the tree size never go beyond logK so processing N elements in worst case requires O(NlogK) time

[@hritwiksom3032]

If we use MaxHeap, we have O(k) space and O(nLogk) time. If we use MinHeap, we have O(1) space and O(n + klogn) time. If k is small such that k~logk, MinHeap gets reduced to ~O(n + logn) MaxHeap gets reduced to ~O(n) If k is of the order n,

[@dipeshsaili4468]

what is quick select method?

[@whysoserious-yj1ku]

Can you explain what is the problem with the quickselect method if there are repeated elements? I just submitted the quickselect method in a problem having test cases with repeated elements and it passed all test cases.

[@NikitaGulabani]

I love your video, it makes learning so easy. Why have you stopped making them ? Can you please create videos on Graphs, Tree and Trie as well

[@lovekushkushwah6409]

hmm

[@chocochips-as]

he is back :)

[@imPriyansh77]

he is back now with his backtracking series...

[@viralprajapati485]

Arre bhai aap kya smjate ho yaar..gajab... Aapne ek dost ki tarah samjaya..Maja aagaya

[@yashagrawal3272]

Here the time complexity is reduced but the space required is increased .But when we use merge sort then that same array can be modified .

[@wttc4]

but in merge-sort, space complexity is O(N) (we use temp array for merging) and here the space is reduced to O(K). Please let me know if I've misunderstood.

[@santokhsingheng]

Thanks Bhai!! you are doing an amazing work. Looking forward for backtracking videos.

[@ishigupta2649]

Sir ur video are very very helpful..thnkuhh sirr.....sir backtracking nd branch nd bound ki bhi upload kr dijeea sir video plzz

[@abhishek.rathore]

Kya samajhaya hai bhai, gfg ke solutions to bilkul samajh nahi aa rahe the. Thanks a lot!!

[@closer9689]

I have two doubts : 1)The work done by heap here can be done by monotonic stack also?2) bhaiya said here that it is not mandatory for array to be sorted ..Then how can we surely say that the top element is our answer?

[@shailajasharma1515]

Thank you so much sir, I am able to understand your videos clearly, you makes the concept very easy to understand, i have implemented this in java, here is my code, //Approach 2: Using Max Heap public class KthSmallestElementInArray { static PriorityQueue maxHeap; static public int findKSmallestElem(int arr[], int k) { for(int a: arr) { maxHeap.add(a); if (maxHeap.size() > k) { maxHeap.poll(); } } return maxHeap.peek(); } public static void main(String[] args) { int arr[] = {8, 9, 5, 2, 6, 7}; int k = 2; System.out.println("Original Array is: " +Arrays.toString(arr)); maxHeap = new PriorityQueue(Collections.reverseOrder()); int ksmallelem = findKSmallestElem(arr, k); System.out.println("Kth Smallest Element is: " + ksmallelem); } }

[@indranilthakur3605]

Where did you learn Heap? I am trying to find a good resource but not able to get one.

[@syedrizwan2203]

for someone who is searching for java code. public class FindKthSmallestElement { public static void main(String[] args) { int arr[]= {7,10,4,3,20,15}; int k=3; int size=6; PriorityQueue maxheap = new PriorityQueue((a,b)-> b-a); for (int i = 0; i < arr.length; i++) { maxheap.add(arr[i]); if(maxheap.size()>3) { maxheap.poll(); } } System.out.println(maxheap.peek()); } }

[@kshitijmishra2716]

any gfg or leetcode link for this quesiton ?

[@piyushsaxena6243]

Thanks a lot for these helpful videos, please keep on making more such videos sir.

[@swastibhagora9914]

Hi bro, in the interview do they ask us to implement the heap using tree?

[@may21136]

It is the same thing. In priority queue, you enter elements by binary searching (O(log(k)). In an ordered binary search tree, insertion will also take O(log(k)). In priority queue, you pop the top element. Likewise, in tree, you just remove the rightmost leaf node. Moreover, C++ STL stores priority queue as a self balancing tree in memory.

[@shubh4793]

Good work here Aditya. your series is really helping me out.

[@the_haryannvi_coder]

Here, we don't need to push every element in queue. After pushing k elements, compare next n-k with top element if they are greater then top then pop top one and push the current one. This will reduce the complexity. If we push each element then complexity will not be N * log(k).

[@deepakprajapati5064]

Thank you So much easy and understandable explanation 👍

[@vaibhavgupta2040]

mact ke londo ki tone mai mact jhalakta hai 🔥🔥

[@shauryasingh8331]

if you use heapify method to build heap in order of n time and pop k times then the overall time complexity will bbe n+klogn. Is this method better thn shownin video?why not?

[@kartikpatidar870]

Aditya bhaiya Great Explanation 🔥

[@arshaanhusain6573]

At 4:28 you said that order of 3 and 4 is not important as compared to 10, ok, so if we insert 6 instead of 15 then the order could be 7 ,3,4,6 and then we pop 7, so how do we get 6 as 3rd maximum?

[@optimus_prime01]

vro after popping 7 , 6 will come on top. That's what max_heap do

[@samarthdixit2036]

bhai kya mast padhate ho aap

[@bestsaurabh]

Why we don't have a delete /erase method in priority_queue stl lib? I guess it will O(n) for any. random element delete? Any help

[@tanmaysahare2353]

Superb teaching Bhai

[@anjalirungta9816]

Liking ur videos too much.plzz make videos for hashing part also.it will be of great help.

[@akhilach6243]

Does it works if the array contains duplicate??

[@anchalmishra2322]

your eplanation is really osm sir g

[@datastructure5253]

What if the repeatation is allowed then like array is - > 2 3 3 5 54 232 5 and k = 3 and it gives us output 3 where maximum 3 is 5 so here your assumption is wrong .

[@rabindrakumar949]

Each element in heap can be entry of key and value

[@cryptowithfaizan8649]

Bhai bahut badiya

[@concnew1420]

Gfg pe sort function ka use kar ke accept hogya pr max heap se tle de rha????

[@deepakkumar-fp8uj]

nhi nhi de rha, ek baar mein submit ho gya!

[@concnew1420]

@@deepakkumar-fp8uj bhai code idhar paste kar do

[@archanoidtalks9393]

Sir are we allowed to use stl in interview

[@ankitgarg5871]

Thanks from toda and my side.😊

[@deepalibajaj9768]

Sir I need one help u have written to take input size and u are using size function...in heap how it can automatically sort

[@palakkotwani8351]

If this question can be done in O(n) then why are we implementing in O(nlogk) ??

[@niveshduppalapudi6885]

how?

[@palakkotwani8351]

@@niveshduppalapudi6885 Using quick sort Here you go:www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

[@shashankmishra484]

Hey, do companies expect quick select algorithm for these kind of questions? Or heap will suffice?

[@harshbhansali1327]

quick select is a must

[@himanshupednekar]

In python from heapq import heappop, heappush, heapify def getKSmallest(arr, k): maxheap = [] heapify(maxheap) for i in arr: heappush(maxheap, -1 * i) if len(maxheap) > k: heappop(maxheap) return maxheap[0] * -1

[@Anjalisinghattri]

why used -1*i?? also in return statement

[@himanshupednekar]

@@Anjalisinghattri since in python their is no library for max heap, so we need to modify min heap and use it. The modification is to multiple value with -1 and use it, no it will work as max heap, and while returning we need to return original value, so one more time multiply it with -1. Clear??

[@Anjalisinghattri]

Ok thankyou

[@SouravKumar-tc2ql]

won't I encounter problems? actually, I will be using your code always is there class for it?

[@himanshupednekar]

@@SouravKumar-tc2ql no, their is no class for max heap in python.

[@shahanaalam2676]

While implementing the same code in gfg practice, it's giving TLE 🙁🙁 Here's my code: // arr : given array // l : starting index of the array i.e 0 // r : ending index of the array i.e size-1 // k : find kth smallest element and return using this function int kthSmallest(int arr[], int l, int r, int k) { priority_queue maxh; for(int i = 0; i k) maxh.pop(); } return maxh.top(); }

[@animeshsingh7060]

this gfg question tells that all elements are distinct. in case of distinct elements we can use quick select method, which is better.

[@govindkrishnalb]

it won't show error now, since they have changed the testcases. We could use quick select method but select random pivot. (leave it to the machine)

[@ganeshkirankumar6910]

PriortyQueue by default is implmenation of MiniHeap, But for this example as we need to use the MaxHep, So in the code above, dont we should use the Compartor.reverseOrder ?? like PriorityQueue max_heap = new PriorityQueue(Compartor.reverseOrder()) ...

[@amansinghal4663]

by default, priority queue is max heap in c++, I dont know about other languages

[@learnhumanity6701]

Hello Sir. Thanks for your video it was a very well-explained video. Can you please upload an explanation for the kth largest odd number in a given range using the greedy approach?

[@SaurabhMelge]

The code can be optimized by checking the current element is smaller than top of the max heap then in that case only pop and push the element in the heap. public static int findKthSmallest(int[] arr, int k) { // Max heap to store the k smallest elements PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); for (int num : arr) { // Add the first k elements directly if (maxHeap.size() < k) { maxHeap.add(num); } else { // Only add if the current element is smaller than the largest element in the heap if (num < maxHeap.peek()) { maxHeap.poll(); // Remove the largest element maxHeap.add(num); // Add the current element } } } // The root of the heap is the k-th smallest element return maxHeap.peek(); }

[@vaibhavpandey5615]

thankyou aditya bhaiya for this beautiful identification rule.

[@anchalpandey2787]

7:46 Input to le hi loge 😂😂 That was epic

[@ankitpandey8967]

Bhaiya agar array main 7 last main hoga to output change nahi hoga

[@GauravKawatrakir]

Thanks for the video. Appreciate your efforts. One more thing can do like "What are the techniques we can use to solve array based problems"? majorly used technique I mean like heap, two pointers, sliding window, etc. These can help to answer Data structure questions. Techniques are not majorly not know to anyone, people have idea "How to solve problem?" but not aware about techniques How to solve problem?

[@manikrangar6357]

sir how the complexity remains nlogk as you push every element once and depending on the conditions pop as well so if i am not wrong total insertion would take nlogn and there are also some deletions so additional xlogn

[@abhinavsharma3819]

Exactly my point.

[@abhinavsharma3819]

A solution come to my mind. When heap.size() becomes k , lets take 4, Means 4 smallest element for present case have been taken already, then just peek() and see if the next element is smaller than the top, accept it, else do not insert Outer i loop: { if h.size()

[@umanggupta5803]

@@abhinavsharma3819 You need to consider all elements in array before declaring the answer

[@omkarvashistha2400]

@@abhinavsharma3819 your solution is good to go just one change that in else part before inserting first pop the top element then insert otherwise the answer that we want will be popped

[@omkarvashistha2400]

@@umanggupta5803 no it is fine all elements are considered but not all are inserted to queue

[@Music-tp8gg]

Comparison karna padega bro! Jo element pop ho raha hai uska

[@Ekam873]

run the code for 1,23,4,5,6 it will not work if yes please explain #include using namespace std; int main() { priority_queueans; int arr[]={1,23,5,9,3}; int k=2; for(int i=0;ik) { ans.pop(); } ans.push(arr[i]); } cout

[@prathamjaiswal3317]

#include using namespace std; int main() { priority_queue ans; int arr[] = {1, 23, 5, 9, 3}; int k = 2; for (int i = 0; i < 5; i++) { ans.push(arr[i]); if (ans.size() > k) { ans.pop(); } } cout

[@beardman4152]

bhai java mai ye priority queue wala concept kaam nahi karta. sirf c++ mai chal rha

[@SunitaGupta-pz8qk]

How to sort the priority queue?

[@HarshGupta-kb5rh]

its is already sorted in descending

[@yashgupta-rs9ro]

Sir array should be sorted because if third element is present in last place in array then it would be popped by algorithm

[@yashgupta-rs9ro]

Sir please answer me

[@TheAdityaVerma]

I dont understand your doubt brother?

[@yashgupta-rs9ro]

Thank you sir for replying me , I understood the concept completely because of your teaching, thank you sir

[@SunitaGupta-pz8qk]

yes, you are right.

[@amus2953]

sir we need to make sure that element which we are pushing in maxheap should be greatest, but we haven't taken this condition in the code. isn't it???

[@harshtita5819]

Bro I tried using this on GFG but it showed TLE. Asked to optimize it. Used scanf and printf and still was being asked to optimize. Used std::sort() instead of heap and submission was successful. Can you clarify ?

[@TheAdityaVerma]

gfg is broken 😂

[@TheAdityaVerma]

btw there is an order of n approach to it using quick sort, you can try it out. But if its getting accept using sort and not heap the ide is certainly broken as sorting will have more time complexity.

[@harshtita5819]

Exactly! I understood that time complexity using heap is much better than using sorting . Anyway, love your content, keep posting videos and help students like us . Thanks 😃

[@subhamchoudhary9123]

but gfg also has O(1) space complexity constraint

[@harshtita5819]

If the constraint is O(1) space complexity then only sorting would give the answer and won't show any TLE error otherwise for an optimized time complexity, heap solution is preferred.

[@ishigupta2649]

Sir jsne aapne stl k use kiya h heap m kya hm 2 stack lekr bhi code bna skte h without vector?

[@debarshibhattacharya9141]

Then we will not get the maximum element on the top every time, so stack is not appropriate here.

[@lakshmanmohanlanka9334]

You can do it using just one stack as well if your sole intention is to have the maximum element on the top of stack

[@AB-qu9uv]

This is not working sir. Below given is the code in java. can u pls help me, what went wrong here? public static int ksmallest(int arr[],int n,int k) { int size=0; PriorityQueue maxh = new PriorityQueue(); for(int i=0;ik) { maxh.poll(); } } return maxh.peek(); }

[@poojaupadhyay6364]

how can we implement this in java? is there any function equivalent to type def and STL in java,which can be used?

[@debasmitamishra9992]

Yes.You can use java.util.PriorityQueue.You can use it for both min and max heap.You can see stackoverflow.com/questions/683041/how-do-i-use-a-priorityqueue

[@poojaupadhyay6364]

@@debasmitamishra9992 thanks a lot dear!

[@abdullahwaqar3024]

what is the time complexity of this program?

[@hareeshkumar922]

O(nlogk)

[@Sharmaji_ki_ldki]

aap bhut acha smjhate ho but the code and the method(java) needed ......

[@prathampahad9788]

class Solution{ public static int kthSmallest(int[] arr, int l, int r, int k){ PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); for(int i = 0;ik){ pq.remove(); } } return pq.peek(); } }

[@prathampahad9788]

Java code @Madhu Sharma

[@ankushroy919]

are bhai heap implement kaise karte hai???????????????????????????????????????

[@SahilSharma-ug8xk]

Thanks bro I have one query. Please clear it. You have made the complexity as nlogk. But lets assume normally we have n as a very large value than k. So logk will not make much difference rather klogn will be much more good. We can build a complete heap of n elements in O(n) time . And then after that we will call extractMin k times from the heap. Which will cost k logn. So overall complexity should be klogn. So which out of these two are better solutions. Please comment.

[@ewananmo2404]

Time complexity of building a complete heap is O(nLogn). - Logn to find an element's place in the heap - n is the number of elements to add to the heap

[@AbdulRahman-sh8lv]

@@ewananmo2404 heapify takes O(n)

[@VikramSingh-hu2hs]

Can't we just use sets

[@debrajroy1290]

sir cant it be done using simple array ds?

[@KeerthiNarayan-c4o]

Yeah that is brute force method This explains logic

[@BlackVoid1998]

Bro time & space complexity of this code ??

[@dhairyashiil]

Thank you

[@ramanprasad5857]

how can we implement the code in python

[@omprakash007]

how to do this question in O(n) ?

[@geekydanish5990]

There is no such sorting algo that provide O(n) don't think so

[@SachinKumar-nz5bn]

use quick select method to do this in O(n)

[@BTEEELavkushYadav]

include using namespace std; int Kthsmallest(int arr[],int k){ priority_queue maxh; for(int i=0;ik){ maxh.pop(); } } return maxh.top(); } int main(){ int n,k; cin>>k; int arr[6]={7,10,4,3,20,15}; Kthsmallest( arr, k); return 0; } can anyone help me out why this code is not giving output

[@184alokkumar2]

cout

[@devangkumawat2258]

in the for loop it should be size of array not size of heap

[@uditkhanna3640]

Priority queue in C++. For Java any suitable predefined Class?

[@suman6327]

java.util.PriorityQueue // By default its a MinHeap For this example : int[] input = new int[]{7,10,4,3,20,15}; int k=3; PriorityQueue pq = new PriorityQueue((x,y)->y-x); // Adding a comparator to convert MinHeap to MaxHeap for (int i : input) { pq.add(i); if(pq.size()>k) pq.remove(); } System.out.println("RESULT : "); System.out.println(pq.peek());

[@youryuvv]

@@suman6327 thank you soo much bro..

[@rukmanabehera5384]

Bhaiya agar 15 k bad 5 hota ek or number toh output 5 ana chahiye lekin app ne jo bataya iss main nahi ayega output 7 ayega🥲🥲plzz recheak kigiye😶😶

[@MukeshKumar-ks9zk]

explanation is wrong. Eg: arr = 10 , 3 , 4. second smallest is needed. solution = 4. but according to him solution will be = 3 which is wrong

[@Ritesh_2401]

@@MukeshKumar-ks9zk bro priority queue me element decreasing order me store hote h top to bottom , he forgot to mention it thats why lot of people have same problem

[@mihirmodi1936]

Listen 3:49 Carefully!!! 7 Will be on top which will be pop out as size > k and Answer = 5

[@bestsaurabh]

If I am coding in C, I should use stack to implement the heap?

[@pavittarkumarazad3259]

Usually heap is implemented by a binary tree. You can use BFS in that case to print the elements in sequence.

[@niranjankumar-uk8sk]

bro please upload vedios on linkedlists and bfs and dfs

[@viraj_singh]

In java we can implement min/max heap in priority queue

[@thesaurabh62057]

thanks sir a lot

[@rishabhbatra3022]

while using heap ,whats the space complexity?? is it O(n).........if yes then i solved a question on gfg and constraints are Expected Time Complexity: O(n) Expected Auxiliary Space: O(1) // but here we have to use O(1) space them how this solution pass? Constraints: 1

[@prasannapm3220]

thanks

[@bat_man1138]

Acha smghaya bhai

[@kamalkumar945]

Thanks Bhaiya

[@ogorganics3752]

Backtracking ki vedios kb daloge sir

[@TheAdityaVerma]

Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️

[@ashishkhar4791]

what if array was 10 4 7 3 5 and k =3 4 will come at top

[@pranaychoubey829]

The priority queue implemented in STL sorts the queue in DSC only, so you shouldn't face that problem.

[@codecode-ig8gy]

class Solution{ public static int kthSmallest(int[] arr, int l, int r, int k) { PriorityQueue maxHeap = new PriorityQueue((a, b) -> b - a); for(int i:arr){ maxHeap.add(i); if(maxHeap.size()>k){ maxHeap.poll(); } } return maxHeap.peek(); } }

[@Sharmaji_ki_ldki]

bhaiya java me b code krke bta dia kro kabhi...........

[@rockerboy4184]

Roses are red Violets are blue Your title is in English But why aren't you

[@mr.kunalk3279]

just to fool you😂

[@louerleseigneur4532]

merci merci

[@TheAdityaVerma]

bienvenu

[@darshan.mehta.]

Sir java me bhi bataiye kaise solve kare

[@akarshjaiswal1622]

❤️❤️❤️

[@TheAdityaVerma]

❤️✌️

[@AmanSingh-pq4rf]

practice.geeksforgeeks.org/problems/kth-smallest-element/0 --- problem link from gfg for those who wanna solve this

[@mihirmodi1936]

Thanks!!!

[@ShadowFighterIndia]

❤❤

[@kuldeepnarayanminj]

lajawaab

[@BeardedBong]

ig u missed the point where we need to sort the k elements at the end of program, thats why the complexity becomes NlogK

[@clashingwithsahib]

no need of sorting k elements in the end of program, the top of minheap will give us kth smallest element always. the complexity of program is NlogK because to insert a element in a heap it requires log(height of heap) time. so to an insert element to heap it require logk time and we are inserting each element to heap so thats why N comes in time complexity so it become NLogK

[@vedantshinde2277]

GFG Link: practice.geeksforgeeks.org/problems/kth-smallest-element5635/1#

[@anitasharmaist]

best !

[@sumitraj8143]

java solution import java.util.Collections; import java.util.PriorityQueue; import java.util.Scanner; public class KthSmallestElement { public static int res(int arr[],int k) { PriorityQueue max=new PriorityQueue(Collections.reverseOrder()); for(int i=0;ik) { max.poll(); } } return max.peek(); } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i

[@JaskaranSingh-hw5jf]

done

[@rabindradocument8934]

Apan

[@unknownname2717]

PLZ USE FAST INPUT OUTPUT WHILE SUBMISSION THE CODE

[@krishnakumar-gc6hb]

I think if it is in English . We all would get benefit for non Hindi speakers

[@devendrasingh4776]

There are lot of channel.

[@pushkarsingh2162]

Bilkul kharab video 😢

[@jawwadakhter5261]

Simple python code ```import heapq l=[7, 10, 4, 3, 20, 15] k=3 heap=[] for i in range(0,len(l)): heapq.heappush(heap,-l[i]) if len(heap)>k: heapq.heappop(heap) print(-heap[0]) ```

[@Aryansingh-fk7hy]

is it a compulsion to import the heapq module?

[@Aryansingh-fk7hy]

can you tell me,why did you use - in -l[i]?

[@parinav10]

@@Aryansingh-fk7hy It is Min Heap by default in the heapq module. Thus, to use it as Max Heap, we take the negative of the values of the list

[@cp65143]

Thanks

[@hiteshwarmehla2267]

public static void main(String[] args) { int[] arr = {1,2,4,7,5,6,3}; int k =3; System.out.println(getKthSmallestInteger(arr, k)); } static int getKthSmallestInteger(int[] arr, int k){ if(arr.length==0){ return -1; } //max Heap PriorityQueue pQueue = new PriorityQueue(Collections.reverseOrder()); for(int i=0;i< arr.length;i++){ pQueue.add(arr[i]); if (pQueue.size()>k){ pQueue.poll(); } } return pQueue.peek(); }