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..😄🙌🏿🙌🏿🙌🏿

[@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

[@shrn]

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

[@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.

[@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..

[@123chen9]

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

[@BackToBackSWE]

You are the og whiteboard youtuber

[@SunilPatel-sf5ng]

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

[@Young10489]

Tushar has become my favorite Indian .

[@casperauto]

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

[@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

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

[@prajaktakarandikar3459]

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

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

[@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

[@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.

[@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

[@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.

[@sungbokang1492]

The easiest approach I've seen. Thanks!

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

[@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.

[@Jeremy0Sea]

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

[@chenhaofeng4842]

The best video for skyline problem

[@zhangbrian102]

Cannot thank more. Do appreciate your great explanation!

[@gauravruhela007]

Tushar bhai....Tussi great ho!

[@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

[@briankarcher8338]

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

[@benpurcell591]

3 mins in , very clear, great explanation

[@kyryloreznykov4959]

The best channel about algorithms on youtube! Thank you.

[@raghav28489]

nope, many of his videos are simply mugged up intuition-less 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]

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

[@josebenardi1554]

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

[@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.

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

[@mbuchove]

Consistently excellent explanations!

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

[@junnunsafoan3977]

Tushar is LC Legend.

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

[@meghna1320]

Thanks Tushar, this is very helpful!

[@firenutz698]

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

[@deathbombs]

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

[@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.

[@Kavishkhullar]

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

[@Atpugtihsrah]

Can't thank you enough for this great explanation!

[@yangli6597]

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

[@chrisniuniu]

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

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

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

[@miketsubasa3611]

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

[@manojamrutharaj9071]

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

[@pianochannel100]

God bless you, you magnificent bastard.

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

[@nairchannel3753]

Couldn't be done better . Thanks .

[@sengineer2554]

Dude this is amazing, thanks for sharing it with us

[@aj_prakash]

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

[@sabeernitb]

Awesome explanation Tushar!!

[@kanthravivvn]

clear explanation Tushar. Keep up the good work !!

[@mukhtarbimurat5106]

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

[@lakshaydulani]

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

[@TheAsltech]

great work Tushar..

[@vijay19841000]

Thanks a lot Tushar. Your explanation was really helpful.

[@reshmichowdhury5189]

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

[@darthvader_]

Great Explanation

[@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.

[@herculean6748]

Great explanation!!

[@kaichenghu3826]

hey man, this is crystal clear

[@talivanov93]

Great explanation. Thank you!

[@algorithmimplementer415]

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

[@patyogesh20]

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

[@VuNguyen-hi3fu]

does the algorithm stays the same when buildings are extended to n-dimension space

[@sj_wanders]

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

[@indrajitbanerjee5131]

Nice explanation.

[@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

[@mylotundinho]

Top man! This is great!

[@smanjunath14]

Great explanation thanks for sharing

[@yunierperez2680]

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

[@AishwaryaRadhakrishnan34]

Amazing! Very Helpful !

[@poojaprasanthi1272]

Thanks Tushar

[@shiwanggupta8608]

use multiset if you are implementing it in c++

[@Brianlane2]

How did you transition from input values of (x1,x2,y) to (x,h,s/e) values?

[@remyaj4837]

each x1,x2,y will become x1,y,s and x2,y,e I believe..

[@jaideeppyne1880]

Does this pass for the case where input array is [[0,2,3],[2,5,3]]? Implemented in C++ its not passing

[@itsjensenkuo]

Awesome tutorial.

[@motivation_hubPJ]

Thanks a lot tushar

[@shashankkumar1974]

Can we use multiset like data structure in C++

[@jasonng3194]

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?

[@BuffPomsky]

access to find and delete will not be around constant time but linear then

[@miracledoh4020]

if you use linkedlist, wouldn't you have to sort it every time you add a new value?that's some poor performance

[@joshuamelo2010]

Very good video

[@ashrafulfuad2967]

you can use extra microphone to record your voice please it will be helpful for viewers and listeners

[@qihan5022]

Best and clearest! TY!

[@sakcee]

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?

[@SudeeptaSood]

thanks tushar!

[@aishwaryagoel149]

For those struggling to understand basic intuition , link with amazing explanation of different appproaches: briangordon.github.io/2014/08/the-skyline-problem.html

[@TheCuriousCurator-Hindi]

Doesn't talk about design of solution. Directly starts with dry run of solution.

[@riturajsarkar6665]

can someone suggest what datastructure should be used for c++ code?