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(); }
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,
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.
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
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
@@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
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) {
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.
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.
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).
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?
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?
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()); } }
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 ?
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.
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 😃
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.
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?
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
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()
@@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
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?
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?
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
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(); }
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)
@@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??
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(); } }
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 .
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()) ...
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());
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(); }
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
#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
@@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
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.
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
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
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(); }
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 !! ✌️❤️
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
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
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(); } }
Works - practice.geeksforgeeks.org/problems/kth-smallest-element/0 int kthSmallest(int arr[], int l, int r, int k) { //code here priority_queuemax_heap; for(int i = l; i k){ max_heap.pop(); } }
Kabhi itne awesome tarike se kisi ne samjahya hi nai. :D
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();
}
thanks bhai bacha liya tune idhar udhar bhatakne se
thankyou so much
@@varshityadav5467 I just also came to check this 😅
FYI..Comparator can be Comparator.reverseOrder() for maxheap of Integer.
PriorityQueue maxHeap = new PriorityQueue(Collections.reverseorder());
This can also be used and very easy to remember for a beginner.
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,
what is quick select method?
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.
Priority -queue
Min big
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
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
@@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
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
@Nahrma Bozonda
Thanks for such beautiful explanation.
@@shrinathdeva6997 the tree size never go beyond logK so processing N elements in worst case requires O(NlogK) time
Arre bhai aap kya smjate ho yaar..gajab... Aapne ek dost ki tarah samjaya..Maja aagaya
Thanks Bhai!! you are doing an amazing work. Looking forward for backtracking videos.
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
hmm
he is back :)
he is back now with his backtracking series...
Kya samajhaya hai bhai, gfg ke solutions to bilkul samajh nahi aa rahe the. Thanks a lot!!
Sir ur video are very very helpful..thnkuhh sirr.....sir backtracking nd branch nd bound ki bhi upload kr dijeea sir video plzz
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);
}
}
Where did you learn Heap? I am trying to find a good resource but not able to get one.
Thanks a lot for these helpful videos, please keep on making more such videos sir.
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 .
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.
Thank you
So much easy and understandable explanation 👍
Good work here Aditya. your series is really helping me out.
Superb teaching Bhai
Aditya bhaiya Great Explanation 🔥
mact ke londo ki tone mai mact jhalakta hai 🔥🔥
7:46
Input to le hi loge 😂😂
That was epic
Hi bro, in the interview do they ask us to implement the heap using tree?
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.
any gfg or leetcode link for this quesiton ?
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
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).
your eplanation is really osm sir g
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?
vro after popping 7 , 6 will come on top. That's what max_heap do
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?
Liking ur videos too much.plzz make videos for hashing part also.it will be of great help.
Bhai bahut badiya
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());
}
}
Thanks from toda and my side.😊
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 ?
gfg is broken 😂
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.
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 😃
but gfg also has O(1) space complexity constraint
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.
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?
thankyou aditya bhaiya for this beautiful identification rule.
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
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
Exactly my point.
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()
@@abhinavsharma3819 You need to consider all elements in array before declaring the answer
@@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
@@umanggupta5803 no it is fine all elements are considered but not all are inserted to queue
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?
Does it works if the array contains duplicate??
Sir are we allowed to use stl in interview
Sir jsne aapne stl k use kiya h heap m kya hm 2 stack lekr bhi code bna skte h without vector?
Then we will not get the maximum element on the top every time, so stack is not appropriate here.
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
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?
Hey, do companies expect quick select algorithm for these kind of questions? Or heap will suffice?
quick select is a must
how can we implement this in java? is there any function equivalent to type def and STL in java,which can be used?
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
@@debasmitamishra9992 thanks a lot dear!
Gfg pe sort function ka use kar ke accept hogya pr max heap se tle de rha????
nhi nhi de rha, ek baar mein submit ho gya!
@@deepakkumar-fp8uj bhai code idhar paste kar do
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();
}
this gfg question tells that all elements are distinct. in case of distinct elements we can use quick select method, which is better.
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)
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
why used -1*i?? also in return statement
@@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??
Ok thankyou
won't I encounter problems? actually, I will be using your code always
is there class for it?
@@SouravKumar-tc2ql no, their is no class for max heap in python.
If this question can be done in O(n) then why are we implementing in O(nlogk) ??
how?
@@niveshduppalapudi6885 Using quick sort
Here you go:www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/
aap bhut acha smjhate ho but the code and the method(java) needed ......
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();
}
}
Java code @Madhu Sharma
sir cant it be done using simple array ds?
Yeah that is brute force method
This explains logic
bhai java mai ye priority queue wala concept kaam nahi karta. sirf c++ mai chal rha
Thank you
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 .
Each element in heap can be entry of key and value
Bhaiya agar array main 7 last main hoga to output change nahi hoga
what is the time complexity of this program?
O(nlogk)
Sir array should be sorted because if third element is present in last place in array then it would be popped by algorithm
Sir please answer me
I dont understand your doubt brother?
Thank you sir for replying me , I understood the concept completely because of your teaching, thank you sir
yes, you are right.
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???
thanks sir a lot
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()) ...
by default, priority queue is max heap in c++, I dont know about other languages
Priority queue in C++.
For Java any suitable predefined Class?
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());
@@suman6327 thank you soo much bro..
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();
}
Acha smghaya bhai
If I am coding in C, I should use stack to implement the heap?
Usually heap is implemented by a binary tree. You can use BFS in that case to print the elements in sequence.
Comparison karna padega bro! Jo element pop ho raha hai uska
how to do this question in O(n) ?
There is no such sorting algo that provide O(n) don't think so
use quick select method to do this in O(n)
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
#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
are bhai heap implement kaise karte hai???????????????????????????????????????
How to sort the priority queue?
its is already sorted in descending
Thanks Bhaiya
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😶😶
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
@@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
Listen 3:49 Carefully!!! 7 Will be on top which will be pop out as size > k and Answer = 5
thanks
how can we implement the code in python
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.
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
@@ewananmo2404 heapify takes O(n)
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
cout
in the for loop it should be size of array not size of heap
Bro time & space complexity of this code ??
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();
}
Can't we just use sets
❤️❤️❤️
❤️✌️
Backtracking ki vedios kb daloge sir
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 !! ✌️❤️
best !
lajawaab
bro please upload vedios on linkedlists and bfs and dfs
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
❤❤
merci merci
bienvenu
In java we can implement min/max heap in priority queue
Roses are red
Violets are blue
Your title is in English
But why aren't you
just to fool you😂
bhaiya java me b code krke bta dia kro kabhi...........
what if array was 10 4 7 3 5 and k =3
4 will come at top
The priority queue implemented in STL sorts the queue in DSC only, so you shouldn't face that problem.
practice.geeksforgeeks.org/problems/kth-smallest-element/0 --- problem link from gfg for those who wanna solve this
Thanks!!!
done
ig u missed the point where we need to sort the k elements at the end of program, thats why the complexity becomes NlogK
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
Sir java me bhi bataiye kaise solve kare
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
I think if it is in English . We all would get benefit for non Hindi speakers
There are lot of channel.
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();
}
}
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])
```
is it a compulsion to import the heapq module?
can you tell me,why did you use - in -l[i]?
@@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
Thanks
Apan
PLZ USE FAST INPUT OUTPUT WHILE SUBMISSION THE CODE
Bilkul kharab video 😢
GFG Link: practice.geeksforgeeks.org/problems/kth-smallest-element5635/1#
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();
}
Works - practice.geeksforgeeks.org/problems/kth-smallest-element/0
int kthSmallest(int arr[], int l, int r, int k) {
//code here
priority_queuemax_heap;
for(int i = l; i k){
max_heap.pop();
}
}
return max_heap.top();
}