Skyline Problem

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

Consistently excellent explanations!

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

thanks brother

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

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

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

Tushar is LC Legend.

Can't thank you enough for this great explanation!

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

Thanks Tushar, this is very helpful!

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

"ssTHHHart"

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

Is this a line-sweep problem?

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

Thanks Tushar

Can we use multiset like data structure in C++

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.

Tushar has become my favorite Indian .

Great Explanation

Thank you.

Does anyone has this algorithm written in C?

how much time did it take for you to solve this?

Thank you very much !!

i do not understand how the new array is created (with 2 times the points) and then sorted in O(n) time

Cannot thank more. Do appreciate your great explanation!

This is a terrible problem like you just need to memorize it

The best video for skyline problem

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!

Great explanation!!

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

If we wanted to use priorityQueue instead of TreeMap, would this help optimize? PQ<BuildingPoint>

Current solution to clarify is:
TreeMap<Integer = height, Integer = occurences>

Great vid Tushar thanks so much. If you are not muslim read about islam Tushar❤

bro why cant you pronounce start as start instead of starhht, btw great video

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

So good to not like

aap please point ko phoint mat bolo. video nhi dekh paa rha

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

Java Code using Priority Queue
class Solution {

public List<List<Integer>> getSkyline(int[][] a) {

List<List<Integer>> res=new ArrayList<>();

List<Triplet> list =new ArrayList<>();

for(int i=0;i<a.length;i++)
{
list.add(new Triplet(a[i][0],a[i][2],true));
list.add(new Triplet(a[i][1],a[i][2],false));

}





Collections.sort(list,new Comparator<Triplet>(){

public int compare(Triplet o1,Triplet o2)
{

//first compare by x.
//If they are same then use this logic
//if two starts are compared then higher height building should be picked first
//if two ends are compared then lower height building should be picked first
//if one start and end is compared then start should appear before end

if(o1.x!=o2.x)
return o1.x-o2.x;

else
{
if(o1.start==true && o2.start==true)
return o2.height-o1.height;

else if(o1.start==false && o2.start==false)
return o1.height-o2.height;

else
{
if(o1.start==true)
return -o1.height;
else
return -o2.height;
}
}
}

});




PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
pq.add(0);
int prevmax=0;

for(Triplet t:list)
{
if(t.start==true)
{
pq.add(t.height);
}

else
{
pq.remove(t.height);
}

int currmax=pq.peek();

if(currmax!=prevmax)
{
List<Integer> temp=new ArrayList<>();
temp.add(t.x);
temp.add(currmax);
res.add(new ArrayList<>(temp));
prevmax=currmax;
}



}
return res;




}

public static class Triplet
{
int x,height;
boolean start;

Triplet(int xx,int yy,boolean s)
{
x=xx;
height=yy;
start=s;
}
}
}

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.

👍

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

3 mins in , very clear, great explanation

Thanks for such a good explanation.

Never talks about intuition. Just directly jumps to the solution. I don't know how people find this helpful. All his videos are like this. No intuition discussion, just directly jumps to the solution like a mugged up robot.

change ur channel name to coding made hell