Short Java Solution with & without Comment


  • 1
    Y

    Thought process:

    I have read some posts and done similar problems. I think the basic idea is to sort different heights first, then maintain a maxHeap to determine which height we should output.

    There's a trick here (taken from others post): negate the height of the starting edges of buildings, so that we can differentiate them from ending edges. When we encounter a starting edge, it's time to activate its height (put on heap). When we encounter an ending edge, we deactivate its height (remove from heap). The heap acts as a container but also provides sorting ability that gives us the max height on top (which is extremely useful).

    The idea behind my code is simple:

    1. Add height of starting edge (don't forget to flip to positive) to result when its greater than previous, put it on heap (activate height).
    2. When we encounter an ending edge, remove from heap (deactivate height), and add height to result only when the height is completely deactivated (does not exist on heap anymore), is currently highest, and doesn't duplicate the last x coordinate of result (since we put max height first we are guaranteed to output the highest one to the result first).

    It handles several cases pretty well.
    e.g. [0, 2, 3], [2, 5, 3]
    We do remove height 3 from heap when we encounter [2,3], but the starting edge of building 2 ([2, -3] if we negate the height) comes first during sorting, and height 3 is still active.

    Same thing with multiple heights on same coordinates. The highest comes first during sorting, and the lower ones would not be added to the result unless they are longer.

    Without comment:

    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> result = new ArrayList<>();
            List<int[]> vertical = new ArrayList<>(buildings.length);
            for (int[] bldg : buildings) {
                vertical.add(new int[]{bldg[0], -bldg[2]});
                vertical.add(new int[]{bldg[1], bldg[2]});
            }
            Collections.sort(vertical, (a, b) -> (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]);
            
            PriorityQueue<Integer> PQ = new PriorityQueue<>((a, b) -> (b - a));
            PQ.offer(0);
            for (int[] h : vertical) {
                int prevY = result.size() == 0 ? 0 : result.get(result.size()-1)[1];
                int prevX = result.size() == 0 ? 0 : result.get(result.size()-1)[0];
                if (h[1] < 0) { // beginning edge of a building
                    if (-h[1] > prevY) {
                        result.add(new int[]{h[0], -h[1]});
                    }
                    PQ.offer(-h[1]); // store height as active
                } else if (h[1] > 0) {  // ending edge of a building
                    PQ.remove(h[1]);    // remove height (deactivate)
                    if (!PQ.contains(h[1]) && h[0] != prevX && h[1] > PQ.peek()) {
                        result.add(new int[]{h[0], PQ.peek()});
                    }
                }
            }
            return result;
        }
    }
    

    With comment:

    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> result = new ArrayList<>();
            List<int[]> vertical = new ArrayList<>(buildings.length);
            for (int[] bldg : buildings) {
                vertical.add(new int[]{bldg[0], -bldg[2]});
                vertical.add(new int[]{bldg[1], bldg[2]});
            }
            // sort building edges by x coordinates, if tied, sort by y coordinates
            Collections.sort(vertical, (a, b) -> (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]);
            // maxPQ (largest element at top, the lambda expression in constructor is very important)
            PriorityQueue<Integer> PQ = new PriorityQueue<>((a, b) -> (b - a));
            PQ.offer(0);    // dummy height represents lowest level
            for (int[] h : vertical) {
                int prevY = result.size() == 0 ? 0 : result.get(result.size()-1)[1];
                int prevX = result.size() == 0 ? 0 : result.get(result.size()-1)[0];
                if (h[1] < 0) { // beginning edge of a building
                    if (-h[1] > prevY) { // only add height when higher than previous
                        result.add(new int[]{h[0], -h[1]});
                    }
                    PQ.offer(-h[1]); // store height as active
                } else if (h[1] > 0) {  // ending edge of a building
                    PQ.remove(h[1]);    // remove height (deactivate)
                    // if statements checks conditions where we don't want to add height to result:
                    // 1. Buildings end on the same x coordinate
                    // 2. Height still active (there is another building with same height and hasn't ended)
                    // 3. Building end is lower than current highest building
                    if (!PQ.contains(h[1]) && h[0] != prevX && h[1] > PQ.peek()) {
                        result.add(new int[]{h[0], PQ.peek()});
                    }
                }
            }
            return result;
        }
    }
    

  • 0
    N

    // if statements checks conditions where we don't want to add height to result:
    // 1. Buildings end on the same x coordinate
    // 2. Height still active (there is another building with same height and hasn't ended)
    // 3. Building end is lower than current highest building
    if (!PQ.contains(h[1]) && h[0] != prevX && h[1] > PQ.peek()) {
    result.add(new int[]{h[0], PQ.peek()});
    }

    Change this if() to be if (h[1] > PQ.peek()) should also work?


  • 0
    Y

    @nuswufei It may not work, because you might repeatedly add the ending edge of buildings that end at the same x coordinate. h[0] != prevX makes sure no repeated ending edges are added. Also we need !PQ.contains(h[1]) because we don't want to add an ending edge when the current height is still active due to multiple continuous buildings that started earlier. Even if we encounter an ending edge, the earlier buildings will make the height still active.


Log in to reply
 

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