# Java two Methods, TreeMap and Divide&Conquer

• Turns out the divide and conquer method is much faster than the popular TreeMap solution.
TreeMap solution: the idea is to process each left edge and right edge and update the current top. If the current top is different from the previous top we need add a point to the result. Be cautious when two edges have the same x coordinates: left edge should appear earlier than right edge; for two left edges, higher one appears first; for two right edges, lower one appears first.

``````    public List<int[]> getSkyline(int[][] buildings) {
int[][] edges = new int[buildings.length*2][2];
for(int i = 0; i < buildings.length; i++) {
edges[i*2] = new int[]{buildings[i][0], -buildings[i][2]};
edges[i*2+1] = new int[]{buildings[i][1], buildings[i][2]};
}
Arrays.sort(edges, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) return o1[1]-o2[1];
else return o1[0]-o2[0];
}
});
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(0, 1);
int prevtop = 0;
for (int[] e : edges) {
if (e[1] < 0) {
map.put(-e[1], map.getOrDefault(-e[1], 0)+1);
} else {
int n = map.get(e[1])-1;
if (n == 0) map.remove(e[1]);
else map.put(e[1], n);
}
if (map.lastKey() != prevtop) result.add(new int[]{e[0], map.lastKey()});
prevtop = map.lastKey();
}
return result;
}
``````

Divide and conquer method: we first get the skylines of the left half and the right half and then merge them together.

``````    private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
int prevtop = 0, h1 = 0, h2 = 0, x;
while (!l1.isEmpty() && !l2.isEmpty()) {
if (l1.peekFirst()[0] < l2.peekFirst()[0]) {
int[] e = l1.removeFirst();
h1 = e[1];
x = e[0];
} else if (l1.peekFirst()[0] > l2.peekFirst()[0]) {
int[] e = l2.removeFirst();
h2 = e[1];
x = e[0];
} else {
int[] e1 = l1.removeFirst(), e2 = l2.removeFirst();
h1 = e1[1];
h2 = e2[1];
x = e1[0];
}
int curtop = Math.max(h1, h2);
if (curtop != prevtop) result.add(new int[]{x, curtop});
prevtop = curtop;
}
return result;
}
private LinkedList<int[]> helper(int[][] buildings, int start, int end) {
if (start == end) {
} else {
int mid = start+(end-start)/2;
result = merge(helper(buildings, start, mid), helper(buildings, mid+1, end));
}
return result;
}
public List<int[]> getSkyline(int[][] buildings) {
if (buildings.length == 0) return new LinkedList<>();
return helper(buildings, 0, buildings.length-1);
}
``````

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