Skyline Problem

[@ChirangiviBhat-i2g]

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"

[@usrenaem]

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!

[@hunarjain4867]

I am here because of LeetCode Daily Challenge and Tushar never fails to deliver..😄🙌🏿🙌🏿🙌🏿

[@shrn]

I've looked at 5-6 tutorials but did not understand what to do, but after watching this video, it became very simple

[@a1988ditya]

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

[@ranga400]

Just Brilliant. Appreciate your patience in going through the code line by line and using the visual to make things clear. Hats off

[@123chen9]

I have to say this is the simplest explaination I have ever seen! Thank you

[@ArijitDebYoutubeChannel]

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.

[@SunilPatel-sf5ng]

Thank you so much sir. I've a got a job because of you. Please continue to deliver awesome algorithms and techniques.

[@casperauto]

Cannot be more clear! It was a lot of work to make this. Thank you.

[@pradeepbalasundaram]

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

[@Bswarup]

I totally agree...We can start with Brute force approach first and then can come to optimized sol..

[@Tejas8272]

Finally able to solve with your explanation after almost 2 days searching debugging others solution /code Thank you👍🏻

[@piyushbansal8004]

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 } }

[@snehalbedmutha1895]

Thank you for this excellent explanation. I wrote your code in Python and I'm getting TLE for one test case (69/70 passed).

[@sidharthbihary2475]

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.

[@larry1285]

nice explanation, the only one I can understand among the tutorials I have found so far

[@larry1285]

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

[@larry1285]

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

[@sungbokang1492]

The easiest approach I've seen. Thanks!

[@Jeremy0Sea]

This is the best explanation on skyline problem I have ever seen so far. Great Job Tushar!

[@syafzal273]

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!

[@Young10489]

Tushar has become my favorite Indian .

[@kyryloreznykov4959]

The best channel about algorithms on youtube! Thank you.

[@raghav28489]

nope, many of his videos are simply mugged up intuition-less explanations

[@BackToBackSWE]

You are the og whiteboard youtuber

[@dargy2368]

You literally saved my life thank you so much. (I understand the homework thanks to you 4 hour before due date).

[@saurabhdsawant]

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.

[@josebenardi1554]

Your videos were really helpful to me during this last semester, thank you for making this available.

[@deathbombs]

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

[@cyf6412]

Tushar's youtube video is really efficient to learn. Thanks!

[@rahul38474]

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.

[@chenhaofeng4842]

The best video for skyline problem

[@zhangbrian102]

Cannot thank more. Do appreciate your great explanation!

[@ignaciogomez1816]

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!!!

[@hannanathar3627]

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

[@briankarcher8338]

This is a crazy awesome explanation of a really hard problem. Hats off to you. You should get back to the KZbin game :)

[@gauravruhela007]

Tushar bhai....Tussi great ho!

[@benpurcell591]

3 mins in , very clear, great explanation

[@biboswanroy6699]

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

[@lallu12343]

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.

[@baurks]

This is great. Finally I am able to solve the problem following your video. Thanks so much!

[@prajaktakarandikar3459]

Anytime the height changes, add the x coordinate and the current max height to the answer.

[@manojamrutharaj9071]

Great explanation Tushar, content is clear with enough Algo tracing examples. I always learn some stuff from your videos. Thanks!

[@mbuchove]

Consistently excellent explanations!

[@vijendrakumarsharma5250]

c++ : can be done via multiset and few implementation changes.. idea is same as above

[@kakkwxt3653]

youtube上讲算法最清楚的频道了。。。膝盖收下

[@yuhaokong]

加我一個

[@anshuman1964]

你是对的

[@Charles-rn3ke]

这哥们在难题上讲的都比华语的频道清楚。

[@BullishBuddy]

translate: This is the clearest explanation among all algo videos on KZbin. Please accept my knees.

[@pullrequest1296]

如果能吧口音纠正一下，就完美了

[@aj_prakash]

Thank you very much for this amazing explanation. Super clear and explained all the edge cases well.

[@firenutz698]

Tushar you explained really well I just wish I could see this solution as easy as you did lol

[@nirmalgurjar8181]

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.

[@miketsubasa3611]

Great Explanation.your explanations are always superb.concept explanation,then edge cases,and then code explanation makes them complete

[@phoenix2623]

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!

[@Madeinchinaagain]

Thanks for pointing this out! I was wondering about this case, too. 2 years later, your comment came in handy!

[@junnunsafoan3977]

Tushar is LC Legend.

[@Kavishkhullar]

saw the compareTo method you wrote. It's a great implementation.

[@tsukisos]

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!

[@yangli6597]

Veryyyyyy clear about this problem!!! Thanks a lot.

[@deathbombs]

If we wanted to use priorityQueue instead of TreeMap, would this help optimize? PQ Current solution to clarify is: TreeMap

[@chrisniuniu]

Thank you very much Tushar sir, you are the best!!!

[@lakshaydulani]

nice question..i thought of the same algo.. happy to see it getting verified here

[@meghna1320]

Thanks Tushar, this is very helpful!

[@Atpugtihsrah]

Can't thank you enough for this great explanation!

[@nairchannel3753]

Couldn't be done better . Thanks .

[@mercuriallabs9]

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).

[@TheAsltech]

great work Tushar..

[@darthvader_]

Great Explanation

[@sengineer2554]

Dude this is amazing, thanks for sharing it with us

[@mukhtarbimurat5106]

Thank you very match! Very clear, especially edge cases!

[@sj_wanders]

Thank you, Tushar. It's an old video but still so useful.

[@smanjunath14]

Great explanation thanks for sharing

[@herculean6748]

Great explanation!!

[@indrajitbanerjee5131]

Nice explanation.

[@poojaprasanthi1272]

Thanks Tushar

[@sabeernitb]

Awesome explanation Tushar!!

[@vijay19841000]

Thanks a lot Tushar. Your explanation was really helpful.

[@mylotundinho]

Top man! This is great!

[@kanthravivvn]

clear explanation Tushar. Keep up the good work !!

[@shreyas.kulkarni]

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.

[@talivanov93]

Great explanation. Thank you!

[@AishwaryaRadhakrishnan34]

Amazing! Very Helpful !

[@cashflow9156]

Great video

[@kaichenghu3826]

hey man, this is crystal clear

[@itsjensenkuo]

Awesome tutorial.

[@qihan5022]

Best and clearest! TY!

[@pianochannel100]

God bless you, you magnificent bastard.

[@reshmichowdhury5189]

Great video. Many thanks for taking time to upload this great video.

[@motivation_hubPJ]

Thanks a lot tushar

[@SudeeptaSood]

thanks tushar!

[@joshuamelo2010]

Very good video

[@qiwang8640]

Thanks a lot! Really Helpful!

[@tanufive]

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

[@RagazzoKZ]

You are absolutely right!

[@tomislavzoricic5656]

Great explanation!

[@marriagedance8657]

great video!

[@yunierperez2680]

Excellent explanation! Are you going to include a divide & conquer solution for this problem in some other video?

[@swapneshchaubal351]

Thanks for the videos dude, appreciate all the hard work you do. Cheers!

[@yh28789]

This is a really good video!

[@lingyongwang2817]

very nice explanation!

[@patyogesh20]

It's not clear what will be the KEY & VALUE in TreeMap though? And, thank you for great explanation

[@kathansanghavi5451]

Thank you very much !!

[@wanghaochen3515]

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.

[@tsukisos]

In c++ you can use std::multiset

[@vivekdhandha3425]

Thanks a ton!

[@akanshkumar2876]

absolute god

[@shiwanggupta8608]

use multiset if you are implementing it in c++

[@algorithmimplementer415]

@Tushar Roy - Coding Made Simple Why did you say that remove from priority queue is not log(n) ?

[@crystinaxinyuzhang3621]

yet how do u remove a non-largest element from the height max-heap?

[@briankarcher8338]

That's the million dollar question. When to, and not to, use a particular data class.