I understood the effort you put in the video when you said in 5:57: "At point thhwu before the shthhart of the building, the maximum value was thhfree"
When I saw this task for the first time I have absolutely no idea how to solve it, no technics/algorithms I knew including priority queue looked like a possible solution. Thanks a lot for that clear explanation!
First of all , would like to say - top class videos and explanation. Really helpful thank u. 1) You dont have to delete items and PQ does not support Log(n) deletes 2) i would keep a heap of objects rather than height alone , as it takes care of case where multiple buildings have same height. Coming to delete , you can ignore deletion - when you do pop_heap you can figure out if that building is stale or not by checking if its x end position is less that the current x position. If its stale just pop it out 3) This is just a line sweep algo application problem
Great explanation! Also, using TreeMap instead of PriorityQueue to improve the remove(Object) operation time complexity from O(N) to O(logN) is a brilliant idea.
Hi Tushar, great videos. Learned a lot. For your future videos I was hoping if you could talk a few minutes about how to develop an intuition in to solving problems. For example, at first the skyline problems seems almost insurmountable even as I think about it in the leisure of my living room. In a pressure cooker situation that is the interview, all my prefrontal functions seem to come to a standstill and there is no hope of even remotely coming close to an approach , let alone write the code for it. It would be of great if you can break down the process of developing an intuition for problems like these. Like for example. How do I solve it by brute force, is there a key insight that can help me solve it better. Why some approaches will work for a certain type of problem and why others wont. How to quickly come up with a subset of approaches that might work. How not to get overwhelmed by the question. For example, the skyline problem can be solved by a heap, or by divide and conquer. Now, how do I come up with either of these approches as if I had never seen this problem before ? - Teach a man to fish and he will eat for a lifetime
Very useful! Great efforts. Appreciate it Tushar Roy. Thank you for uploading. The code part helps a lot also would be perfect if we can just discuss naive approaches for the problems at the start. Thanks again.
Great video. I like that you went over the algorithm and why it works unlike some of the DP videos where the answer is explained but now how it was arrived at. Also, love that you have python code!
beautifully explained. thanks Tushar. the best part of problem solving is you discuss the idea of the solution before jumping directly into the algorithm part.
Great work Tushar...You made it very clear especially the edge cases. For those who write in c++ the compare function for sorting the buildings is bool operator()(bb a, bb b) { if (a.x != b.x) { return a.x < b.x; } else if (a.isStart and b.isStart) { return a.y > b.y; //building with larger height } else if (!a.isStart and !b.isStart) { return a.y < b.y; //building with smaller height } else { return a.isStart; //if end and another start we will consider start building first } }
The sorting algorithm for buildingPoints class is key here for finding start, end, and skyline height: (this.isStart ? -this.height : this.height - o.isStart ? -o.height : o.height) if same x, sort the start points by height, ignore the end points if not same x, sort by x
Pretty simple! I saw almost all your videos and I have to say that you made a great job. It would be helpful if you can share your interview experiences too Congratulations!!!
00:02 Merge overlapping buildings to form skyline view 02:35 Algorithm for finding skyline points 04:53 Tracking building heights to determine skyline changes. 07:11 Process the input points and prioritize based on start and end values 09:39 Understanding edge cases in the Skyline Problem 12:00 Examining time complexity of the problem. 14:06 Ordering rules for buildings based on heights 16:14 Updating building heights and recording the maximum height 18:03 Tracking and updating the current max height 19:58 Explanation of adding and deleting building points based on conditions 21:53 Deleting a single count from map affects height calculation
I cannot find a built-in method to delete a specific item from priority queue in python. Could you tell me what should I do to solve the problem using the method taught in the video? Thank you so much
I got this question in a final round for an internship and even though I barely understood the question I still somehow managed to come up with this solution, I didn’t even understand the answer I was giving the interviewer.
Have a feeling that PQ/heap is an overfit for this problem. If the given input of n intervals is exploded to 2n entries with x1:y and (x2-1):y, then sorted on x, and then deduped for x and y both (with different rules) and expanded for missing entries in that deduping pass itself, we can still get to an O(nlogn) worst case.
Just one thing, how are you supposed to remove an element from a priority queue if it wasn't the head of it? There's no way to iterate a c++ STL or Java queue. I think a better explanation is a max heap not a priority queue.
There is also a divide and conquer approach. This approach is nice. But in cpp I had to use multimap and create a priority queue according to the requirement for removing any node. In an interview it seems to be very lengthy
Thanks Tushar sir for explaining, Heap is not the most appropriate data structure to be used in this problem, this is a classic use case for ordered_map, I was silly to think this could be replaced with ordered_set but didn't consider the case of duplicate heights. TreeMap() is the solution.
good solution, but I feel the time complexity depends a lot on the priority queue implementation. I have not come across any implementation of priority queue that supports delete operation in real world in O(logn). So lets suppose deletion is supported in O(x). Then time complexity of solution becomes O(n.x).
Thanks for the video, amazing explanation!! Another case handled inadvertently by the comparator, and is worth mentioning is that, if this.x == other.x && this. height == other.height, the point that has isStart = true comes before the point with isStart = false, in order to avoid errorenously flipping the height back to lower and making a wrong critical point in result. Thanks!
There is one thing I dont understand. Is there a need to use a Queue? As you have suggested, you can also use TreeMap. but how about using a linked list?
Sorting and creating the points, then extracting random values from the PQ adds extra complexity that could be avoided just by updating the result points.
I understood the effort you put in the video when you said in 5:57: "At point thhwu before the shthhart of the building, the maximum value was thhfree"
I am here because of LeetCode Daily Challenge and Tushar never fails to deliver..😄🙌🏿🙌🏿🙌🏿
When I saw this task for the first time I have absolutely no idea how to solve it, no technics/algorithms I knew including priority queue looked like a possible solution. Thanks a lot for that clear explanation!
First of all , would like to say - top class videos and explanation. Really helpful thank u.
1) You dont have to delete items and PQ does not support Log(n) deletes
2) i would keep a heap of objects rather than height alone , as it takes care of case where multiple buildings have same height. Coming to delete , you can ignore deletion - when you do pop_heap you can figure out if that building is stale or not by checking if its x end position is less that the current x position. If its stale just pop it out
3) This is just a line sweep algo application problem
Great explanation! Also, using TreeMap instead of PriorityQueue to improve the remove(Object) operation time complexity from O(N) to O(logN) is a brilliant idea.
Hi Tushar, great videos. Learned a lot. For your future videos I was hoping if you could talk a few minutes about how to develop an intuition in to solving problems. For example, at first the skyline problems seems almost insurmountable even as I think about it in the leisure of my living room. In a pressure cooker situation that is the interview, all my prefrontal functions seem to come to a standstill and there is no hope of even remotely coming close to an approach , let alone write the code for it. It would be of great if you can break down the process of developing an intuition for problems like these. Like for example. How do I solve it by brute force, is there a key insight that can help me solve it better. Why some approaches will work for a certain type of problem and why others wont. How to quickly come up with a subset of approaches that might work. How not to get overwhelmed by the question. For example, the skyline problem can be solved by a heap, or by divide and conquer. Now, how do I come up with either of these approches as if I had never seen this problem before ? - Teach a man to fish and he will eat for a lifetime
I totally agree...We can start with Brute force approach first and then can come to optimized sol..
Just Brilliant. Appreciate your patience in going through the code line by line and using the visual to make things clear. Hats off
Very useful! Great efforts. Appreciate it Tushar Roy. Thank you for uploading.
The code part helps a lot also would be perfect if we can just discuss naive approaches for the problems at the start. Thanks again.
You are the og whiteboard youtuber
Cannot be more clear! It was a lot of work to make this. Thank you.
Thank you so much sir. I've a got a job because of you. Please continue to deliver awesome algorithms and techniques.
Great video. I like that you went over the algorithm and why it works unlike some of the DP videos where the answer is explained but now how it was arrived at. Also, love that you have python code!
You literally saved my life thank you so much. (I understand the homework thanks to you 4 hour before due date).
Thank you for this excellent explanation. I wrote your code in Python and I'm getting TLE for one test case (69/70 passed).
I've looked at 5-6 tutorials but did not understand what to do, but after watching this video, it became very simple
beautifully explained. thanks Tushar. the best part of problem solving is you discuss the idea of the solution before jumping directly into the algorithm part.
Great work Tushar...You made it very clear especially the edge cases.
For those who write in c++ the compare function for sorting the buildings is
bool operator()(bb a, bb b) {
if (a.x != b.x) {
return a.x < b.x;
}
else if (a.isStart and b.isStart) {
return a.y > b.y; //building with larger height
}
else if (!a.isStart and !b.isStart) {
return a.y < b.y; //building with smaller height
}
else {
return a.isStart; //if end and another start we will consider start building first
}
}
The best channel about algorithms on youtube! Thank you.
nope, many of his videos are simply mugged up intuition-less explanations
I have to say this is the simplest explaination I have ever seen! Thank you
Anytime the height changes, add the x coordinate and the current max height to the answer.
The sorting algorithm for buildingPoints class is key here for finding start, end, and skyline height:
(this.isStart ? -this.height : this.height - o.isStart ? -o.height : o.height)
if same x, sort the start points by height, ignore the end points
if not same x, sort by x
Finally able to solve with your explanation after almost 2 days searching debugging others solution /code
Thank you👍🏻
Pretty simple! I saw almost all your videos and I have to say that you made a great job.
It would be helpful if you can share your interview experiences too
Congratulations!!!
This is the best explanation on skyline problem I have ever seen so far.
Great Job Tushar!
Your videos were really helpful to me during this last semester, thank you for making this available.
This is a crazy awesome explanation of a really hard problem. Hats off to you. You should get back to the UA-cam game :)
00:02 Merge overlapping buildings to form skyline view
02:35 Algorithm for finding skyline points
04:53 Tracking building heights to determine skyline changes.
07:11 Process the input points and prioritize based on start and end values
09:39 Understanding edge cases in the Skyline Problem
12:00 Examining time complexity of the problem.
14:06 Ordering rules for buildings based on heights
16:14 Updating building heights and recording the maximum height
18:03 Tracking and updating the current max height
19:58 Explanation of adding and deleting building points based on conditions
21:53 Deleting a single count from map affects height calculation
All 3 edge cases are covered if we mark -ve height for start the building and now if starts are same then height can be matched.
nice explanation, the only one I can understand among the tutorials I have found so far
I cannot find a built-in method to delete a specific item from priority queue in python. Could you tell me what should I do to solve the problem using the method taught in the video? Thank you so much
since your python version does not pass the test 35 either, I know you use dict and use max(queue.keys()) to get the maximum
Tushar has become my favorite Indian .
Hey, thanks a lot Tushar! Your explaination for the edge cases helped me solve the bugs I've been having for a whole day, LOL.. Keep it up buddy!
The easiest approach I've seen. Thanks!
youtube上讲算法最清楚的频道了。。。膝盖收下
加我一個
你是对的
这哥们在难题上讲的都比华语的频道清楚。
translate: This is the clearest explanation among all algo videos on UA-cam. Please accept my knees.
如果能吧口音纠正一下，就完美了
I got this question in a final round for an internship and even though I barely understood the question I still somehow managed to come up with this solution, I didn’t even understand the answer I was giving the interviewer.
If we wanted to use priorityQueue instead of TreeMap, would this help optimize? PQ
Current solution to clarify is:
TreeMap
Have a feeling that PQ/heap is an overfit for this problem. If the given input of n intervals is exploded to 2n entries with x1:y and (x2-1):y, then sorted on x, and then deduped for x and y both (with different rules) and expanded for missing entries in that deduping pass itself, we can still get to an O(nlogn) worst case.
does the algorithm stays the same when buildings are extended to n-dimension space
Just one thing, how are you supposed to remove an element from a priority queue if it wasn't the head of it? There's no way to iterate a c++ STL or Java queue. I think a better explanation is a max heap not a priority queue.
In c++ you can use std::multiset
There is also a divide and conquer approach. This approach is nice. But in cpp I had to use multimap and create a priority queue according to the requirement for removing any node. In an interview it seems to be very lengthy
Tushar bhai....Tussi great ho!
3 mins in , very clear, great explanation
The best video for skyline problem
Great explanation Tushar, content is clear with enough Algo tracing examples. I always learn some stuff from your videos. Thanks!
Thanks Tushar sir for explaining, Heap is not the most appropriate data structure to be used in this problem, this is a classic use case for ordered_map, I was silly to think this could be replaced with ordered_set but didn't consider the case of duplicate heights.
TreeMap() is the solution.
c++ : can be done via multiset and few implementation changes.. idea is same as above
Thank you very much for this amazing explanation. Super clear and explained all the edge cases well.
if we use priorityQueue then there is no way to maintain a counter for height repetition and i guess its required to have that. So PQ is not an option
You are absolutely right!
Tushar's youtube video is really efficient to learn. Thanks!
Tushar is LC Legend.
Tushar you explained really well I just wish I could see this solution as easy as you did lol
Great Explanation.your explanations are always superb.concept explanation,then edge cases,and then code explanation makes them complete
Cannot thank more. Do appreciate your great explanation!
good solution, but I feel the time complexity depends a lot on the priority queue implementation. I have not come across any implementation of priority queue that supports delete operation in real world in O(logn). So lets suppose deletion is supported in O(x). Then time complexity of solution becomes O(n.x).
@Tushar Roy - Coding Made Simple Why did you say that remove from priority queue is not log(n) ?
It's not clear what will be the KEY & VALUE in TreeMap though? And, thank you for great explanation
This is great. Finally I am able to solve the problem following your video. Thanks so much!
Dude this is amazing, thanks for sharing it with us
at any given point x, the skyline is max of current buildings, so why cant we just iterate and keep a max of current buildings which fall on ith x?
Thanks for the video, amazing explanation!! Another case handled inadvertently by the comparator, and is worth mentioning is that, if this.x == other.x && this. height == other.height, the point that has isStart = true comes before the point with isStart = false, in order to avoid errorenously flipping the height back to lower and making a wrong critical point in result. Thanks!
Thanks for pointing this out! I was wondering about this case, too. 2 years later, your comment came in handy!
yet how do u remove a non-largest element from the height max-heap?
That's the million dollar question. When to, and not to, use a particular data class.
Consistently excellent explanations!
How did you transition from input values of (x1,x2,y) to (x,h,s/e) values?
each x1,x2,y will become x1,y,s and x2,y,e I believe..
There is one thing I dont understand. Is there a need to use a Queue? As you have suggested, you can also use TreeMap. but how about using a linked list?
access to find and delete will not be around constant time but linear then
if you use linkedlist, wouldn't you have to sort it every time you add a new value?that's some poor performance
Excellent explanation! Are you going to include a divide & conquer solution for this problem in some other video?
Thank you very much Tushar sir, you are the best!!!
Doesn't talk about design of solution. Directly starts with dry run of solution.
Does this pass for the case where input array is [[0,2,3],[2,5,3]]? Implemented in C++ its not passing
saw the compareTo method you wrote. It's a great implementation.
Is this a line-sweep problem?
Can't thank you enough for this great explanation!
clear explanation Tushar. Keep up the good work !!
Veryyyyyy clear about this problem!!! Thanks a lot.
how much time did it take for you to solve this?
Top man! This is great!
you can use extra microphone to record your voice
please it will be helpful for viewers and listeners
Awesome explanation Tushar!!
Thanks Tushar, this is very helpful!
Great Explanation
great work Tushar..
Couldn't be done better . Thanks .
Thanks a lot Tushar.
Your explanation was really helpful.
Great explanation!!
Can we use multiset like data structure in C++
Great video. Many thanks for taking time to upload this great video.
Sorting and creating the points, then extracting random values from the PQ adds extra complexity that could be avoided just by updating the result points.
Thank you very match! Very clear, especially edge cases!
can someone suggest what datastructure should be used for c++ code?
hey man, this is crystal clear
God bless you, you magnificent bastard.
I dont find a need for priority queue or anything
I do this in O(n^2)
with just one for loop and the other for loop is smaller
nice question..i thought of the same algo.. happy to see it getting verified here
Thank you, Tushar. It's an old video but still so useful.
Best and clearest! TY!
Thanks a lot! Really Helpful!
Nice explanation.
Thanks Tushar
Amazing! Very Helpful !
Great video
Great explanation. Thank you!
Great explanation thanks for sharing