You are a Pro Bro . Every Time I stuck on Problem I just type the problem and in suffix Tech Dose. and Boom.... Bagwan Prakat !!!! Really Appreciate your efforts towards community .
Of all the videos in this playlist this one is little bit tricky. It would be such a blessing to have an elder brother like you. Thank you very much for all the efforts you are making.
@@techdose4u please make a video on bit manipulation leetcode 1486 question It is an easy problem but I am not able to solve it in O(1) time complexity...read so many articles on it but still can't figure out how it is working
Sir, Thank you for the awesome videos. Please also consider making videos on various Patterns of Interview problems, examples and how to build strong intuition to spot these patterns. example: Two pointers, Monotonic queue, heap, two heaps, when to use union-find vs graphs, intervals/scheduling etc
Simple code for the last approach time complexity: O(nlog2k) space complexity: O(k) (for using priority queue) //compare function for priority queue class Compare { public: bool operator() (const ListNode* n1, const ListNode* n2) { return (n1->val) > (n2->val); } }; class Solution { public: ListNode* mergeKLists(vector& lists) {
if(lists.size() == 0) return NULL; //MIMP edge case for interview priority_queue pq;
//pushing first nodes of all the lists into the priority queue for(int i=0; inext != NULL){ pq.push(node->next); } }
No...It would be NlogK only....Since we are traversing each list at the same time, so O(N+k) for traversal and each traversal will take O(logK) time to push/pop from Min-Heap
Randomly searched for the solution, and here I am on this channel...very nice approach and easily explained. Thank you so much for all the leetcode problems you explained. Just subscribed.
@@techdose4u only thing is if you could do it in java too and explain as you write the code from the beginning. Just my opinion though. It’s hard to just copy lots of code at once.
What is the point of creating 'ptr' when you could use 'lists'? Why initialize ptr? Is it because that's a dummy ListNode since we need to use 'lists' later on? Why do we need to create a pointer for that when we could just iterate through the 'lists' and go to the next ListNode?
Great video sir . Just wanted some clarification in divide and conquer approach that isn't the heap method better than it as in divide and conquer we are also using stack memory ?
// Without using list index in priority queue class Solution { struct node { ListNode *curr; //Current node node(ListNode *a) { curr = a;
} }; struct compare { bool operator()(node a, node b) { return a.curr->val >b.curr->val; } }; public: ListNode* mergeKLists(vector& lists) { int k = lists.size(); if(k==0) return NULL; ListNode *head,*tail; head=tail=NULL; priority_queue heap; //Assign all the current ptrs and BUILD_HEAP for(int i=0;inext) //Push newly pointed node if not NULL heap.push(node(tail->next));
//Make list with rest of the nodes while(!heap.empty()) { ListNode *temp=heap.top().curr; //Pop root node heap.pop();
tail->next=temp; //Add newnode to list tail=tail->next; if(temp->next) //Push newly pointed node if not NULL heap.push(node(temp->next)); } return head; } };
if there isn't an explanation by tech dose for a leetcode problem i feel lost. You are the best!
Thanks 😊
You are a Pro Bro . Every Time I stuck on Problem I just type the problem and in suffix Tech Dose. and Boom.... Bagwan Prakat !!!!
Really Appreciate your efforts towards community .
😂
Of all the videos in this playlist this one is little bit tricky.
It would be such a blessing to have an elder brother like you.
Thank you very much for all the efforts you are making.
👍🏼
@@techdose4u please make a video on bit manipulation leetcode 1486 question It is an easy problem but I am not able to solve it in O(1) time complexity...read so many articles on it but still can't figure out how it is working
Now I got one more question covered. Thanks!! Please make video on "Find median in a stream".
Sure
Use 2 priority que simultaneously...
Insertion sort might also help there
Sir, Thank you for the awesome videos. Please also consider making videos on various Patterns of Interview problems, examples and how to build strong intuition to spot these patterns.
example: Two pointers, Monotonic queue, heap, two heaps, when to use union-find vs graphs, intervals/scheduling etc
Sure
Your explanation is really good.. the way you giving the example and explained it ,it’s really fab. man.
great content! Please continue doing this. Planning on completing all your videos.
Great
me too :)
Simple code for the last approach
time complexity: O(nlog2k)
space complexity: O(k) (for using priority queue)
//compare function for priority queue
class Compare
{
public:
bool operator() (const ListNode* n1, const ListNode* n2)
{
return (n1->val) > (n2->val);
}
};
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
if(lists.size() == 0) return NULL; //MIMP edge case for interview
priority_queue pq;
//pushing first nodes of all the lists into the priority queue
for(int i=0; inext != NULL){
pq.push(node->next);
}
}
return head;
}
};
Awesome explanation.
I think the time complexity of the last 2 approaches will be O(N * k * log(k)). Correct me if I'm wrong.
@TECHDOSE
No...It would be NlogK only....Since we are traversing each list at the same time, so O(N+k) for traversal and each traversal will take O(logK) time to push/pop from Min-Heap
Randomly searched for the solution, and here I am on this channel...very nice approach and easily explained. Thank you so much for all the leetcode problems you explained. Just subscribed.
Sir please make playlist on string hard problem on leetcode. Thankyou so much sir for your videos. 💥💥🙏🙏
Please recommend this when I start String algo playlist.
Best Channel for average students
😅
Time complexity is wrong for last 2 . It should be NKlog(k) . Please correct it
Here build Heap,percolate up is being called implicitly by the c++ priority_queue?
Great job
Amazing! Keep doing these please
Sure :)
@@techdose4u only thing is if you could do it in java too and explain as you write the code from the beginning. Just my opinion though. It’s hard to just copy lots of code at once.
What is the point of creating 'ptr' when you could use 'lists'? Why initialize ptr? Is it because that's a dummy ListNode since we need to use 'lists' later on? Why do we need to create a pointer for that when we could just iterate through the 'lists' and go to the next ListNode?
great explanation.
The starting code of heap approach is confusing can someone explaine?
Bro please solve Alien Dictionary. Thanks 👍🏻
I will try
@@techdose4u thanks bro🙏🏻👍🏻
Welcome
First approach takes o(n) and not o(nk) i think. Can u double check?
sir do all leetcode problems as well codechef
Thank you sir
very well explained , thanks a lot
Welcome :)
Excellent choice of question 😉
Thanks :)
👍 5methods, wow, thank You
Hello sir,
Please explain Tower of Honoi if possible. Because I have tried to get it since last one year but never satisfied with those videos.
Sure. I will include those when I do recursion.
@@techdose4u thanks!
good work bro, keep it up.
Thanks
sir did you make any video for merge k sorted arrays?
Thanks, Which are you using for the annotations and making the drawings.
thanks for sharing
Very helpful video, Thank you :)
Welcome :)
Thanks!
Welcome
Why can't we push all nodes from all lists to the heap and then pop all elements till heap becomes empty? That will even sort K unsorted Linked lists.
Great video sir . Just wanted some clarification in divide and conquer approach that isn't the heap method better than it as in divide and conquer we are also using stack memory ?
You can implement it iteratively.
thank u sir..!!
Welcome :)
Why not to push all Nodes into heap with one iteration which is O(N*logk), then simply pop O(N*logk) and build the final linked list?
That is O(N logN)
which software do you use for teaching bhaiya?
what about space complexity ti create heap of size k?
O(K)
Why am I not getting TLE when I submit O(nk) solution ?
add a
while(true){ }
snippet in the code
Heap approach using array of pointers
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
struct node{
ListNode* curr;
int idx;
node(ListNode* a,int x){
curr=a;
idx=x;
}
};
struct compare{
bool operator()(node a,node b){
return a.curr->val > b.curr->val;
}
};
ListNode* Solution::mergeKLists(vector &A) {
priority_queue minh;
int k =A.size();
vector ptr(k);
for(int i=0;inext;
// crucial
if(ptr[index]!=NULL) minh.push(node(ptr[index],index));
while(!minh.empty()){
ListNode* temp=minh.top().curr;
index=minh.top().idx;
minh.pop();
tail->next=temp;
tail=tail->next;
ptr[index]=ptr[index]->next;
if(ptr[index]!=NULL) minh.push(node(ptr[index],index));
}
return head;
}
in heap approach why don't we add all elements in the min heap first and then pop them 1 by 1
Coz its complexity would then be o(nlogn) same as that of merge sort.
I don't think we need to maintain an index array.
17:00
Heap Algorithm won't work for such examples:
K = 4
L1 = [1 2 3 4]
L2 = [0 5 10 15]
L3 = [2 4 8 10]
L4 = [3 9 27 81]
Expected Output:
0 1 2 2 3 3 4 4 5 8 9 10 10 15 27 81
Output according to this solution:
0 1 2 2 3 3 4 5 4 8 9 10 10 15 27 81
Reason:
Heap of size K cannot accommodate all smallest numbers from all K arrays at once.
Heap has to retain max K element at once, not more than that. Heap size will be less than K only when you have exhausted one or more linked list.
The best
hey guyz what if we start td old videos in background on mute so that he will get more watch time on his channel and ultimately earn more.
Bro please solve "can place flowers" Leetcode 605
I will try
@@techdose4u thanks bro!
bless u
🙏🏽
waiting 😇
Nice :)
Can anyone explain compare function in priority_queue
Samson q2u?
// Without using list index in priority queue
class Solution {
struct node {
ListNode *curr; //Current node
node(ListNode *a)
{
curr = a;
}
};
struct compare {
bool operator()(node a, node b)
{
return a.curr->val >b.curr->val;
}
};
public:
ListNode* mergeKLists(vector& lists) {
int k = lists.size();
if(k==0)
return NULL;
ListNode *head,*tail;
head=tail=NULL;
priority_queue heap;
//Assign all the current ptrs and BUILD_HEAP
for(int i=0;inext) //Push newly pointed node if not NULL
heap.push(node(tail->next));
//Make list with rest of the nodes
while(!heap.empty())
{
ListNode *temp=heap.top().curr; //Pop root node
heap.pop();
tail->next=temp; //Add newnode to list
tail=tail->next;
if(temp->next) //Push newly pointed node if not NULL
heap.push(node(temp->next));
}
return head;
}
};
read about islam man❤
Thanks!
Welcome 😀