# Java divide and conquer solution beats 96%

• The basic idea is divide the buildings into two subarrays, calculate their skylines respectively, then merge two skylines together.

``````public class Solution {
public List<int[]> getSkyline(int[][] buildings) {
return merge(buildings, 0, buildings.length-1);
}

private LinkedList<int[]> merge(int[][] buildings, int lo, int hi) {
if(lo > hi) {
return res;
} else if(lo == hi) {
return res;
}
int mid = lo+(hi-lo)/2;
LinkedList<int[]> left = merge(buildings, lo, mid);
LinkedList<int[]> right = merge(buildings, mid+1, hi);
int leftH = 0, rightH = 0;
while(!left.isEmpty() || !right.isEmpty()) {
long x1 = left.isEmpty()? Long.MAX_VALUE: left.peekFirst()[0];
long x2 = right.isEmpty()? Long.MAX_VALUE: right.peekFirst()[0];
int x = 0;
if(x1 < x2) {
int[] temp = left.pollFirst();
x = temp[0];
leftH = temp[1];
} else if(x1 > x2) {
int[] temp = right.pollFirst();
x = temp[0];
rightH = temp[1];
} else {
x = left.peekFirst()[0];
leftH = left.pollFirst()[1];
rightH = right.pollFirst()[1];
}
int h = Math.max(leftH, rightH);
if(res.isEmpty() || h != res.peekLast()[1]) {
}
}
return res;
}
}
``````

• How isn't anyone noticing and upvoting this solution???

• Nice and clean divide and conquer solution.

But cannot pass the test `[[1,2,1],[2147483646,2147483647,2147483647]]`.
Because if `x1 == x2 == Integer.MAX_VALUE`, maybe `left` or `right` is empty, and thus it will cause `NullPointerException`.

So the else statement should be modified as

``````else {
x = x1;
leftH = left.isEmpty() ? 0 : left.pollFirst()[1];
rightH = right.isEmpty() ? 0 : right.pollFirst()[1];
}
``````

• @JieJackyZhang Thank you for your test case. But I have tried it and my code do pass this test case. I think the reason is you may use Integer.MAX_VALUE instead of Long.MAX_VALUE for `long x1 = left.isEmpty()? Long.MAX_VALUE: left.peekFirst()[0]`. If you use Integer.MAX_VALUE, you may have the problem because x itself may be Integer.MAX_VALUE.

• @yzjJosh Yes, you are right. It will not be a problem if you use `Long.MAX_VALUE`. Thank you.

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