# Time complexity O(nlogn). Simple and Clean. Divide and Conquer. Merge Sort. Upvote me!!!!!!!!

• Simple and straight foward.

``````public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result=new ArrayList<>();
if(buildings.length==0) return result;
List<SkyLine> res=mergeSort(buildings,0,buildings.length-1);
return result;
}

//Merge sort method. We can achieve ^(nlogn) here as well
// T(n)=2*T(n/2)+n......
public List<SkyLine> mergeSort(int[][]buildings,int start,int end){
List<SkyLine> result=new ArrayList<SkyLine>(),left,right;
if(start==end){//base case
return result;
}
int mid=start+(end-start)/2;
left=mergeSort(buildings,start,mid);
right=mergeSort(buildings,mid+1,end);
int p1=0,p2=0,h1=0,h2=0,newX=0,newY=0;
//It is similar to two way merge sort, always pick smaller x from two ends
//p1 and p2 are the pointers. h1, h2 is current height, yhey aways get updated when picking new skylines.
//I could have got rid of newX and new Y. But for the purpose of readability, I keep them here. They are new skylines'
//x and y (left and height).
SkyLine s1,s2;
while(p1<left.size()&&p2<right.size()){
s1=left.get(p1);
s2=right.get(p2);
if(s1.x<s2.x){
h1=s1.y;
p1++;
}else if(s1.x>s2.x){
h2=s2.y;
p2++;
}else{
h1=s1.y;
h2=s2.y;
p1++;
p2++;
}
newX=Math.min(s1.x,s2.x);
newY=Math.max(h1, h2);
if(result.isEmpty() || newY != result.get(result.size() - 1).y){//When we are adding new ones, make sure nothing duplicate
}
}
return result;
}
``````

class SkyLine{
int x,y;
public SkyLine(int x,int y){
this.x=x;
this.y=y;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.