378. Kth Smallest Element in a Sorted Matrix | Priority Queue | Binary Search on Answer
Vložit
- čas přidán 8. 05. 2024
- In this video, I'll talk about how to solve Leetcode 378. Kth Smallest Element in a Sorted Matrix | Priority Queue | Binary Search on Answer
Leetcode 74. Search a 2D Matrix II Binary Search II Binary Search Tree - • Leetcode 74. Search a ...
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/aryan-0077
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms
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 = czcams.com/video/SmxdebjWvfs/video.html
(Write on YT - Leetcode 786 by Aryan Mittal) (Look at above's Video Time stamps for Min Heap approach)
Keepp rocking ❤
Brilliant Presentation style is superb.
your intuition building is nice , 14:03
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.
Awesome
Yaaaaay, First Comment!!!!!!
❤️❤️ yeah coding kart broo 🫂
very good
damn i used quickselect which is almost as good as bimary search on answers
Will there be a video on todays leetcode POTD?
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 ❤
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