# 408ms Java Solution using linked list

• Each time a new building is introduced, we adjust the skyline accordingly. A linked list is used to store the skyline so that node can be easily inserted, appended and removed.

``````public class Solution {
class KeyPoint {
public int key;
public int height;
public KeyPoint next = null;

public KeyPoint(int key, int height) {
this.key = key;
this.height = height;
}

}

public static int[] getKeyPoint(int key, int height) {
int[] kp = new int[2];
kp[0] = key;
kp[1] = height;
return kp;
}

public List<int[]> getSkyline(int[][] buildings) {
for (int[] building:buildings) {
int l = building[0], r = building[1], h= building[2];
// insert left point
while (prevKP.next != null && prevKP.next.key <= l) prevKP = prevKP.next;
int preHeight = prevKP.height;
if (prevKP.key == l) prevKP.height = Math.max(prevKP.height, h);
else if (prevKP.height < h) {
KeyPoint next = prevKP.next;
prevKP.next = new KeyPoint(l, h);
prevKP = prevKP.next;
prevKP.next = next;
}
// insert right point and update points in between
KeyPoint prev = prevKP, cur = prevKP.next;
while (cur != null && cur.key < r) {
preHeight = cur.height;
cur.height = Math.max(cur.height, h);
if (cur.height == prev.height)
prev.next = cur.next;
else
prev = cur;
cur = cur.next;
}
if (prev.height != preHeight && prev.key != r && (cur == null || cur.key != r)) {
KeyPoint next = prev.next;
prev.next = new KeyPoint(r, preHeight);
prev.next.next = next;
}
}
// convert to List<int[]>
List<int[]> list = new ArrayList<int[]>();
while (cur != null) {
if (cur.height != prev.height)
prev = cur;
cur = cur.next;
}
return list;
}
}``````

• Can you please add some explanation here ? It will make it easy to understand

• What's the time complexity? It likes O(N) but it is not, since it needs to find positions to add the new building.

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