Kth smallest element in an array | Kth Largest element in an array | Heap | Priority Queue

Heap Tree| Priority Queue | Data Structure and Algorithm | 180daysofcode #dsa #heap #india

00:00 Introduction
1:29 Problem 1 - Method 1 - Kth smallest Element (Brute Force)
3:51 Calculating Time and Space Complexity
5:23 Method 2 - Kth Smallest Element ( using min heap)
9:36 Calculating Time and Space Complexity
12:30 Method 3 - Kth Smallest Element
25:41 Calculating Time and Space Complexity
31:05 Code Part - Kth Smallest Element
35:22 Problem 2 - Kth Largest Element
43:11 Calculating Time and Space Complexity
45:58 Code Part - Kth Largest Element
50:28 Problem 3 - Kth Largest Element in a Stream (HomeWork)
52:33 Problem 4 - Sum of element between K1 and K2 Smallest Element
53:31 Method 1 - Sum of element between K1 and K2 Smallest Element
54:38 Method 2 - Sum of element between K1 and K2 Smallest Element
59:40 Code Part - Sum of element between K1 and K2 Smallest Element
1:06:14 Last Note

Day 188/180, #180daysofcode #180 hard

We are doing 180 days challenge and going to complete the whole course within the duration with quality content on Youtube. I am on the mission to create a tech revolution in our country and in upcoming future we want to create a tech which will create many jobs in India.

Video will come on Mon-Fri at 6am in the morning

DSA Course for free
C++ Free Course
Rohit Negi DSA Course C++
Coder Army DSA Course c++
Function in C++
Pointers in C++.
Strings
Vector
Introduction to Recursion

[CoderArmy]

3 Approaches se Problem Solve kiya hai, Bataiye fr, Maja Aaaya...

[SajanKumar-efur]

the mentor, the instructor, specility - chamka dena concept ko, selfless, Thank you

[Pallab]

3:Kth largest element in a stream:
vector<int> kthLargest(int k, int arr[], int n) {
// code here
//using min_heap
priority_queue<int, vector<int>, greater<int>>p;
vector<int>ans;
for(int i=0;i<n;i++)
{
p.push(arr[i]);
if(p.size()<k)
{
ans.push_back(-1);
}
else
{
while(p.size()>k)
p.pop();
ans.push_back(p.top());
}
}
return ans;
}

[Aniruddha_Mukherjee]

Problem 2 :

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {

priority_queue<int, vector<int>, greater<int>> pq;

for(int i = 0; i<k; ++i) {
pq.push(nums[i]);
}

for(int i=k; i<nums.size(); ++i) {
if(pq.top() < nums[i]) {
pq.pop();
pq.push(nums[i]);
}
}

return pq.top();

}
};

[suryxnz]

This is the best dsa course on yt but underrated . Thank you bhaiya for putting this much effort.

[ShivshankarKumaryadav-mf]

1:08:02 tak bhaiya persent. atendance please😊😊

[allinonemoviesyt]

50:33 Homework - kth largest element in a stream

vector<int> kthLargest(int k, int arr[], int n) {
// code here
vector<int> ans;

priority_queue<int, vector<int>, greater<int>> pq;

for(int i=0; i<k; i++){
pq.push(arr[i]);
if(pq.size() != k) ans.push_back(-1);
else ans.push_back(pq.top());
}

for(int i=k; i<n; i++){
if(pq.top() < arr[i]){
pq.pop();
pq.push(arr[i]);
}
ans.push_back(pq.top());
}

return ans;
}

[kapilkhandelwal]

mza aa agya bhaiya itne dino baad lecture dekh k

[ManojSinghRawat-xw]

bhaiya hum appke sath hamesha bane rahenga ❤
aaj bhi last tak😎

[smitallunawat]

Too good explanation... feel hi aa gaya bhaiya!!

[manish_kumar_iitg]

3: Kth largest element in a stream:-
vector<int>ans(n);
priority_queue<int, vector<int>, greater<int>> p;

for(int i = 0; i<k-1; i++){
ans[i] = -1;
p.push(arr[i]);
}

p.push(arr[k-1]);
ans[k-1] = p.top();

for(int i = k; i<n;i++){
if(p.top() < arr[i]){
p.push(arr[i]);
p.pop();
}
ans[i] = p.top();
}
return ans;

[allinonemoviesyt]

59:23 Homework :

Time Complexity :-

1. sabse pehle hum K1 elements ko priority queue me daalege to uska time time compleity hoga = O(K1logK1)
2. fir (N-K1) elements ko top elements se compare krege aur insert krege heap me, to uska time complexity hoga = O((N-K1)logK1)
3. fir hum (K2-1) elements ka new priority queue bnayege uska time complexity hoga = O((K2-1)log(K2-1))
4. fir hum (N-K2+1) elements ko top elements se compare krege aur insert krege heap me, to uska time complexity hoga= O((N-K2+1)log((K2-1)))

5. fir hum K1 elements waale heap ke elements ka sum nikalege uska time complexity hoga = O(K1logK1)
6. fir hum K2-1 elements waale heap ke elements ka sum nikalege uska time complexity hoga = O((K2-1)log(K2-1))

overall time complexity in sb ka addition hoga


Space Complexity :-
1. K1 elements ka priority queue bnayege to space use hoga = O(K1)
2. K2-1 elements ka priority queue bnayege to space use hoga = O(K2-1)

overall space complexity hoga = O(K1 + K2 -1)

[sdtedit]

bhaiya aap ni hote to pata ni hamara kya hota itna accha content log apne paid cources me bhi nahi dete

[techmjo]

Bhaiya Hashing Playlist wali Video kb Aayengi
???

[abhinayjangde]

1:06:25 Sum of elements between k1'th and k2'th smallest elements | Bhaiya Maine Aise banaya hai

long long sumBetweenTwoKth( long long A[], long long N, long long K1, long long K2)
{
// Creating Min Heap
priority_queue<long long, vector<long long>, greater<long long>> pq;
for(int i=0; i<N; i++){
pq.push(A[i]);
}

long long sum = 0;
while(K1){
pq.pop();
K1--;
K2--;
}
K2=K2-1;
while(K2){
sum+=pq.top();
pq.pop();
K2--;
}
return sum;
}

[itshirdeshk]

Time and space complexity of last question:

Time Complexity -> O(nlogk2)
Space Complexity -> O(k1 + k2) -> O(k2), if you are using priority queue || O(1), if you are using step-down approach.

[ankitchoudhary]

don't know why but ajj ka class kuch jyada interesting thi😎😎😎😎😎