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


  • 0
    C

    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);
        for(SkyLine temp:res) result.add(new int[]{temp.x,temp.y});
        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
    		result.add(new SkyLine(buildings[start][0],buildings[start][2]));
    		result.add(new SkyLine(buildings[start][1],0));
    		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
                result.add(new SkyLine(newX,newY));
            }
    	}
    	while(p1<left.size()) result.add(new SkyLine(left.get(p1).x,left.get(p1++).y)); //Add what's left over
    	while(p2<right.size()) result.add(new SkyLine(right.get(p2).x,right.get(p2++).y)); //Add what's left over
    	return result;
    }
    

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


Log in to reply
 

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