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!
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
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
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.
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!
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 } }
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.
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
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!!!
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.
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
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
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.
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).
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?
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!
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!
I am here because of LeetCode Daily Challenge and Tushar never fails to deliver..😄🙌🏿🙌🏿🙌🏿
Just Brilliant. Appreciate your patience in going through the code line by line and using the visual to make things clear. Hats off
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
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..
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.
I have to say this is the simplest explaination I have ever seen! Thank you
Thank you so much sir. I've a got a job because of you. Please continue to deliver awesome algorithms and techniques.
You are the og whiteboard youtuber
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.
I've looked at 5-6 tutorials but did not understand what to do, but after watching this video, it became very simple
Cannot be more clear! It was a lot of work to make this. Thank you.
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!
This is the best explanation on skyline problem I have ever seen so far.
Great Job Tushar!
You literally saved my life thank you so much. (I understand the homework thanks to you 4 hour before due date).
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
}
}
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.
Tushar has become my favorite Indian .
Thank you for this excellent explanation. I wrote your code in Python and I'm getting TLE for one test case (69/70 passed).
Your videos were really helpful to me during this last semester, thank you for making this available.
Finally able to solve with your explanation after almost 2 days searching debugging others solution /code
Thank you👍🏻
Tushar bhai....Tussi great ho!
The best channel about algorithms on youtube! Thank you.
nope, many of his videos are simply mugged up intuition-less explanations
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
The best video for skyline problem
The easiest approach I've seen. Thanks!
This is a crazy awesome explanation of a really hard problem. Hats off to you. You should get back to the UA-cam game :)
3 mins in , very clear, great explanation
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!!!
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!
Cannot thank more. Do appreciate your great explanation!
Tushar's youtube video is really efficient to learn. Thanks!
Anytime the height changes, add the x coordinate and the current max height to the answer.
Great explanation Tushar, content is clear with enough Algo tracing examples. I always learn some stuff from your videos. Thanks!
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.
Consistently excellent explanations!
Tushar is LC Legend.
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.
This is great. Finally I am able to solve the problem following your video. Thanks so much!
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.
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
c++ : can be done via multiset and few implementation changes.. idea is same as above
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
Great Explanation.your explanations are always superb.concept explanation,then edge cases,and then code explanation makes them complete
If we wanted to use priorityQueue instead of TreeMap, would this help optimize? PQ
Current solution to clarify is:
TreeMap
Great Explanation
Great explanation!!
Can't thank you enough for this great explanation!
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
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!
Thanks Tushar, this is very helpful!
Tushar you explained really well I just wish I could see this solution as easy as you did lol
Veryyyyyy clear about this problem!!! Thanks a lot.
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.
Thank you very much Tushar sir, you are the best!!!
great work Tushar..
Couldn't be done better . Thanks .
Nice explanation.
Top man! This is great!
@Tushar Roy - Coding Made Simple Why did you say that remove from priority queue is not log(n) ?
Thank you very much for this amazing explanation. Super clear and explained all the edge cases well.
Thanks Tushar
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).
Dude this is amazing, thanks for sharing it with us
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
Awesome explanation Tushar!!
clear explanation Tushar. Keep up the good work !!
Great explanation thanks for sharing
Thanks a lot tushar
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.
It's not clear what will be the KEY & VALUE in TreeMap though? And, thank you for great explanation
saw the compareTo method you wrote. It's a great implementation.
hey man, this is crystal clear
God bless you, you magnificent bastard.
Thank you very match! Very clear, especially edge cases!
Amazing! Very Helpful !
Thanks a lot Tushar.
Your explanation was really helpful.
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..
Very good video
Great explanation. Thank you!
Great video. Many thanks for taking time to upload this great video.
youtube上讲算法最清楚的频道了。。。膝盖收下
加我一個
你是对的
这哥们在难题上讲的都比华语的频道清楚。
translate: This is the clearest explanation among all algo videos on UA-cam. Please accept my knees.
如果能吧口音纠正一下，就完美了
Best and clearest! TY!
thanks tushar!
Excellent explanation! Are you going to include a divide & conquer solution for this problem in some other video?
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?
Can we use multiset like data structure in C++
Does this pass for the case where input array is [[0,2,3],[2,5,3]]? Implemented in C++ its not passing
Awesome tutorial.
does the algorithm stays the same when buildings are extended to n-dimension space
Thank you, Tushar. It's an old video but still so useful.
Great video
This is a really good video!
Thanks a lot! Really Helpful!
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!
Thanks for the videos dude, appreciate all the hard work you do. Cheers!
very nice explanation!
nice question..i thought of the same algo.. happy to see it getting verified here