Skyline Problem
HTML-код
- Опубликовано: 7 фев 2025
- / tusharroy25
github.com/mis...
github.com/mis...
www.educative....
You are given a set of n rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the x position of the left edge, the x position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night.
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..😄🙌🏿🙌🏿🙌🏿
I've looked at 5-6 tutorials but did not understand what to do, but after watching this video, it became very simple
Just Brilliant. Appreciate your patience in going through the code line by line and using the visual to make things clear. Hats off
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
Thank you so much sir. I've a got a job because of you. Please continue to deliver awesome algorithms and techniques.
I have to say this is the simplest explaination I have ever seen! Thank you
Cannot be more clear! It was a lot of work to make this. Thank you.
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.
You are the og whiteboard youtuber
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..
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).
Finally able to solve with your explanation after almost 2 days searching debugging others solution /code
Thank you👍🏻
Thank you for this excellent explanation. I wrote your code in Python and I'm getting TLE for one test case (69/70 passed).
Tushar has become my favorite Indian .
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!
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.
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.
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.
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
Your videos were really helpful to me during this last semester, thank you for making this available.
The best video for skyline problem
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
The easiest approach I've seen. Thanks!
The best channel about algorithms on youtube! Thank you.
nope, many of his videos are simply mugged up intuition-less explanations
This is a crazy awesome explanation of a really hard problem. Hats off to you. You should get back to the RUclips game :)
3 mins in , very clear, great explanation
Tushar bhai....Tussi great ho!
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!
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
}
}
Cannot thank more. Do appreciate your 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!!!
Tushar's youtube video is really efficient to learn. Thanks!
This is great. Finally I am able to solve the problem following your video. Thanks so much!
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!
youtube上讲算法最清楚的频道了。。。膝盖收下
加我一個
你是对的
这哥们在难题上讲的都比华语的频道清楚。
translate: This is the clearest explanation among all algo videos on RUclips. Please accept my knees.
如果能吧口音纠正一下，就完美了
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.
Tushar is LC Legend.
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
Anytime the height changes, add the x coordinate and the current max height to the answer.
If we wanted to use priorityQueue instead of TreeMap, would this help optimize? PQ
Current solution to clarify is:
TreeMap
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
Dude this is amazing, thanks for sharing it with us
Can't thank you enough for this great explanation!
Thanks Tushar, this is very helpful!
Great Explanation
Great Explanation.your explanations are always superb.concept explanation,then edge cases,and then code explanation makes them complete
Great explanation!!
Thank you very much for this amazing explanation. Super clear and explained all the edge cases well.
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.
Couldn't be done better . Thanks .
great work Tushar..
Thank you very much Tushar sir, you are the best!!!
hey man, this is crystal clear
Nice explanation.
Top man! This is great!
Great video. Many thanks for taking time to upload this great video.
Awesome explanation Tushar!!
clear explanation Tushar. Keep up the good work !!
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).
Very good video
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 a lot Tushar.
Your explanation was really helpful.
c++ : can be done via multiset and few implementation changes.. idea is same as above
Amazing! Very Helpful !
Thank you very match! Very clear, especially edge cases!
Best and clearest! TY!
Great explanation thanks for sharing
saw the compareTo method you wrote. It's a great implementation.
Great explanation. Thank you!
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.
nice question..i thought of the same algo.. happy to see it getting verified here
Thanks Tushar
This is a really good video!
Thank you, Tushar. It's an old video but still so useful.
Thanks for the videos dude, appreciate all the hard work you do. Cheers!
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 a lot tushar
Excellent explanation! Are you going to include a divide & conquer solution for this problem in some other video?
does the algorithm stays the same when buildings are extended to n-dimension space
Great video
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
Awesome tutorial.
thanks tushar!
you can use extra microphone to record your voice
please it will be helpful for viewers and listeners
Thanks a lot! Really Helpful!
Can we use multiset like data structure in C++
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
how much time did it take for you to solve this?
God bless you, you magnificent bastard.
great video!
It's not clear what will be the KEY & VALUE in TreeMap though? And, thank you for great explanation
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.
Great explanation!
Does this pass for the case where input array is [[0,2,3],[2,5,3]]? Implemented in C++ its not passing