30 lines: Clean and concise code using Java 8 features, with clear comments


  • 0
    H
    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            // https://briangordon.github.io/2014/08/the-skyline-problem.html
            // 1/3: Collect and sort critical points, left edge uses negative height,
            // each building has 2 critical points.
            List<int[]> heights = new ArrayList<>();
            for (int[] b : buildings) {
                heights.add(new int[]{b[0], -b[2]});
                heights.add(new int[]{b[1], b[2]});
            }
            // sort by the left edge and then the right edge
            Collections.sort(heights, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
            
            // 2/3: Use a treeMap to store all the current heights, from largest to smallest
            List<int[]> skyline = new ArrayList<>();
            TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
            // 3/3: Add the first 0 height to start,
            heightMap.put(0, 0);
            // don't forget the previous height!
            int prevHeight = 0;
            for (int[] h : heights) {
                // left edge, add the height to the map
                if (h[1] < 0) {
                    heightMap.put(-h[1], heightMap.getOrDefault(-h[1], 0) + 1);
                } else {
                    heightMap.computeIfPresent(h[1], (key, oldVal) -> oldVal == 1 ? null : oldVal - 1);
                }
                int currHeight = heightMap.firstKey();
                if (prevHeight != currHeight) {
                    skyline.add(new int[]{h[0], currHeight});
                    prevHeight = currHeight;
                }
            }
            return skyline;
        }
    }
    

    The above code beats ~60%, due to lambda expression being slow in Java 8. However, I still prefer using lambda since that will make the code cleaner. Better for whiteboard writing.


Log in to reply
 

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