Once for all, explanation with clean Java code(O(n^2)time, O(n) space)


  • 80
    M

    Though I came up with a solution using PriorityQueue and BST, this problems still confuses me. To make it more clear, I went through it several times and investigated several good solutions on this forum.

    Here is my explanation which tries to make understanding this easier and may help you write a bug-free solution quickly.

    When visiting all start points and end points in order:

    Observations:

    1. If a position is shadowed by other buildings

       1. height of that building is larger than the building to which current
           position belong;
       2. the start point of that building must be smaller(or equal to) than this
           position;
       3. the end point of that building must be larger(or equal to) than this
           position;
      

    Tus we have:

    1. when you reach a start point, the height of current building immediately
        takes effect which means it could possibly affect the contour or shadow
        others when mixed with other following buildings;
    2. when you reach a end point, the height of current building will stop its
        influences;
    3. our target exists at the position where height change happens and there
        is nothing above it shadowing it;
    

    Obviously, to implement the idea that 'current height takes effect' and 'find out whether current height is shadowed by other buildings', we need a mechanism to store current taking effect heights, meanwhile, figure out which one is the maximum, delete it if needed efficiently, which hints us to use a priority queue or BST.

    Thus, our algorithm could be summarised in following pseudo code:

    for position in sorted(all start points and all end points)
           if this position is a start point
                  add its height
           else if this position is a end point
                  delete its height
           compare current max height with previous max height, if different, add
           current position together with this new max height to our result, at the
           same time, update previous max height to current max height;
    

    To implement this algorithm, here are some concrete examples:

    1. In my implementation, I use a PriorityQueue to store end point values when visiting a start point, and store the [height, end point value] into a TreeMap. Thus:
      1. when moving to next start point value, I can compare the next start point value with elements in PriorityQueue, thus achieving visiting all start points and end points in order(exploits the fact that start points are already sorted);
      2. Meantime, I can get current max height from TreeMap in O(logn);
      3. However, to delete a height when visiting a end point, I have to use 'map.values.remove()' which is a method defined in Collection interface and tends to be slower(O(n) is this case, plz correct me if I'm wrong);

    My code can be found at https://leetcode.com/discuss/62617/short-and-clean-java-solution-heap-and-treemap

    1. Following is wujin's implementation(plz refer to https://leetcode.com/discuss/54201/short-java-solution). This one is quite straightforward, clean and clever.

    Firstly, please notice what we need to achieve:

      1. visit all start points and all end points in order;
      2. when visiting a point, we need to know whether it is a start point or a
          end point, based on which we can add a height or delete a height from
          our data structure;
    

    To achieve this, his implementation:

      1. use a int[][] to collect all [start point, - height] and [end point, height]
          for every building;
      2. sort it, firstly based on the first value, then use the second to break
          ties;
    

    Thus,

      1. we can visit all points in order;
      2. when points have the same value, higher height will shadow the lower one;
      3. we know whether current point is a start point or a end point based on the
          sign of its height;
    

    His code is as follows(clear and concise) as reference with my comment(again, https://leetcode.com/discuss/54201/short-java-solution):

    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> height = new ArrayList<>();
        for(int[] b:buildings) {
            // start point has negative height value
            height.add(new int[]{b[0], -b[2]});
            // end point has normal height value
            height.add(new int[]{b[1], b[2]}); 
        }
    
        // sort $height, based on the first value, if necessary, use the second to
        // break ties
        Collections.sort(height, (a, b) -> {
                if(a[0] != b[0]) 
                    return a[0] - b[0];
                return a[1] - b[1];
        });
    
        // Use a maxHeap to store possible heights
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
    
        // Provide a initial value to make it more consistent
        pq.offer(0);
    
        // Before starting, the previous max height is 0;
        int prev = 0;
    
        // visit all points in order
        for(int[] h:height) {
            if(h[1] < 0) { // a start point, add height
                pq.offer(-h[1]);
            } else {  // a end point, remove height
                pq.remove(h[1]);
            }
            int cur = pq.peek(); // current max height;
      
            // compare current max height with previous max height, update result and 
            // previous max height if necessary
            if(prev != cur) {
                result.add(new int[]{h[0], cur});
                prev = cur;
            }
        }
        return result;
    }
    

    Hopefully now, you can write a good solution in a blink with good understanding...


  • 0
    L

    Thank you for the help. I was puzzled until I saw your explanation.


  • 6
    N

    This is O(n^2) because removal in a PQ is O(n)


  • -2
    M

    Removing from PQ is O(1) time and heapify operation takes O(log N) time.


  • 0
    K

    No. Take a look at https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html. linear time for the remove(Object) and contains(Object) methods.
    In priority queue, find the element takes O(n), heapify takes O(longn), so it's O(n).


  • 2
    M

    Yes, my bad. Removing from PQ is O(N) time. Thanks for pointing out.


  • 0

    Nice explanation, but could you please re-format it to make it easier to read; for now there are many words cannot be read due to its format. Thanks in advance!


  • 1
    M

    I'm glad it helps


  • 1
    M

    Sure. Pls check again.


  • 0
    S

    I think you need add sth like "int cur = pq.isEmpty()? 0 : pq.Peek();" since there might be gaps between rctgls.


  • 0
    S

    @StRush I guess no need. For the last building of overlapped buildings, the height of turning point is 0 and we already have "pq.offer(0)" at the beginning. There won't be any chance of pq is empty according to this algorithm.


  • 0
    R

    Thanks for the explanation. This is the only I can understand among all comments.


  • 0
    D

    Can someone explain why in the solution you need to sort by the start value? Does this leverage something? Not to sure why you need to do this.


  • 1
    Z

    @DanielMan97 Why we sort the critical points this way? The reason is that we want to scan from left to right, so we sort all the critical points (both start and end point) with its position.

    If two points' position are the same, we always put the start point at first, and then break the tie with their height.
    The point here is, since for each position, there may exist multiple critical point with different height, and we only want the one is tallest. So for this situation, it's quite important to add the point with maximal height first to heap first, then if the later height is the same as the previous one, we can skip it and avoid adding wrong answer.


  • 0
    Z

    Just want to say thanks again~
    I really like your explanation and final solution, it's concise and clean.


  • 0
    Y
    This post is deleted!

  • 0
    W

    a more complicate but more efficient way

     public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> result = new ArrayList<>();
            if(buildings.length == 0) return result;
            PriorityQueue<int[]> height = new PriorityQueue<>((a,b)->(b[0] - a[0]));
            int[][] bases = new int[buildings.length * 2][3];
            Set<Integer> removed = new HashSet<>();
            for(int i = 0;i < buildings.length;i++){
                bases[i * 2] = new int[]{buildings[i][0],i,1};
                bases[i * 2 + 1] = new int[]{buildings[i][1],i,-1};
            }
            Arrays.sort(bases,(a,b)->(a[0] - b[0]));
            height.offer(new int[]{0,-1});
            int lastHeight = 0;
            for(int i = 0;i < bases.length;){
                // int[] first = bases[i];
                int[] first = bases[i];
                int k = i;
                while(k < bases.length && first[0] == bases[k][0]) k++;
                for(;i < k;i++){
                    int[] base = bases[i];
                    if(base[2] == 1){
                        height.offer(new int[]{buildings[base[1]][2],base[1]});
                    }else{
                        removed.add(base[1]);
                    }
                }
                while(removed.contains(height.peek()[1])) height.poll();
                int currentHeight = height.peek()[0];
                if(currentHeight != lastHeight){
                    result.add(new int[]{first[0],currentHeight});
                    lastHeight = currentHeight;
                }
            }
            return result;
        }
    

  • 0
    A

    thanks for you explanation. :)


  • 0
    S

    @maplain use a hashmap to maintain the number of the point with same height (when it's start point , add 1 to the count of the height, because you need to enqueue, and when it's end point, just minus one to the count of the heigh, and for the element on the top of the heap , just need to check whether its count is positive, otherwise just pop it), you don't need to remove from the heap with O(n) complexity. And the total complexity will be O(n logn)


  • 0
    O

    Very elegant !! what a great thinking!


Log in to reply
 

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