One major optimisation in priority queue approach i missed, which is optimising O(n*m*log(k)) to O(k*log(k)), this can be achieved using Priority Queue (this time Min Heap), in which = . Intuition - Remove smallest k-1 elements then, what so ever is remaining first element in data-structure is kth smallest Element. [Remove smallest element - Min Heap] . Step1 - Push column0 all elements in Min Heap. Step2 - Start removing elements from above Min Heap [remove k-1 elements], on each removal size of min Heap will decrease by 1, so add next element in that same row to min Heap to make size of min Heap back to K. Step 3 - After applying above operation k-1 times, we will be left with data structure having k or less elements, but top of that min heap will be kth Smallest element. time complexity = O(n + klog(k)) Documentation with Diagram (Solution 2) - tinyurl.com/24lnp87w . Video Dry Run of this approach in this Video = th-cam.com/video/SmxdebjWvfs/w-d-xo.html (Write on YT - Leetcode 786 by Aryan Mittal) (Look at above's Video Time stamps for Min Heap approach)
Aryan Bhai Binary Search ke upar bhi Crash Course Nikaalon Please, badi confusion hoti hai ki right = mid karna hai ya right = mid -1 aaj ke daily ke editorial mein bhi yahi confusion hui
Nhi bhai, in my solutions it is always mid-1, i never taught to take high as mid, thus we follow same template in all binary search questions, low is always mid + 1. But yeah, a crash course on this is also very important. ( will be soon live on codewithAryan channel )❤️🫂
@@ARYANMITTAL Bro can we make a video on basics of every data structure like what is priority queue , max heap like that for some important data structures. I know there are many vedios but your explanation is soooo good even I code in python I watching and able to understand.
![Leetcode 378. Kth Smallest Element in a Sorted Matrix [Java]](/img/n.gif)
One major optimisation in priority queue approach i missed, which is optimising O(n*m*log(k)) to O(k*log(k)), this can be achieved using Priority Queue (this time Min Heap), in which =
.
Intuition - Remove smallest k-1 elements then, what so ever is remaining first element in data-structure is kth smallest Element. [Remove smallest element - Min Heap]
.
Step1 - Push column0 all elements in Min Heap.
Step2 - Start removing elements from above Min Heap [remove k-1 elements], on each removal size of min Heap will decrease by 1, so add next element in that same row to min Heap to make size of min Heap back to K.
Step 3 - After applying above operation k-1 times, we will be left with data structure having k or less elements, but top of that min heap will be kth Smallest element.
time complexity = O(n + klog(k))
Documentation with Diagram (Solution 2) - tinyurl.com/24lnp87w
.
Video Dry Run of this approach in this Video = th-cam.com/video/SmxdebjWvfs/w-d-xo.html
(Write on YT - Leetcode 786 by Aryan Mittal) (Look at above's Video Time stamps for Min Heap approach)
Brilliant Presentation style is superb.
your intuition building is nice , 14:03
Keepp rocking ❤
Very well explained.
We can also do this in O(n) time complexity, leetcode has given a research paper pdf in their question, by the way. Nice Explanation 😍
I have noticed, bro you have stopped hiding the company names.
Aryan Bhai Binary Search ke upar bhi Crash Course Nikaalon Please,
badi confusion hoti hai
ki
right = mid
karna hai ya
right = mid -1
aaj ke daily ke editorial mein bhi yahi confusion hui
Nhi bhai, in my solutions it is always mid-1, i never taught to take high as mid, thus we follow same template in all binary search questions, low is always mid + 1. But yeah, a crash course on this is also very important. ( will be soon live on codewithAryan channel )❤️🫂
@@ARYANMITTAL Cool
thank u
You Are Awesome ❤
Will there be a video on todays leetcode POTD?
very good
Awesome
damn i used quickselect which is almost as good as bimary search on answers
Yaaaaay, First Comment!!!!!!
❤️❤️ yeah coding kart broo 🫂
When I find an answer in the interview is like: 16:10
Bro today's Leetcode problem 🥺
Already live on channel bro ❤️
@@ARYANMITTAL Bro can we make a video on basics of every data structure like what is priority queue , max heap like that for some important data structures. I know there are many vedios but your explanation is soooo good even I code in python I watching and able to understand.
Greate your posting such awesome content, but I don't like the way you over express things in your video