Java divide and conquer solution beats 96%


  • 26
    Y

    The basic idea is divide the buildings into two subarrays, calculate their skylines respectively, then merge two skylines together.

    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            return merge(buildings, 0, buildings.length-1);
        }
        
        private LinkedList<int[]> merge(int[][] buildings, int lo, int hi) {
            LinkedList<int[]> res = new LinkedList<>();
            if(lo > hi) {
                return res;
            } else if(lo == hi) {
                res.add(new int[]{buildings[lo][0], buildings[lo][2]});
                res.add(new int[]{buildings[lo][1], 0});
                return res;
            } 
            int mid = lo+(hi-lo)/2;
            LinkedList<int[]> left = merge(buildings, lo, mid);
            LinkedList<int[]> right = merge(buildings, mid+1, hi);
            int leftH = 0, rightH = 0;
            while(!left.isEmpty() || !right.isEmpty()) {
                long x1 = left.isEmpty()? Long.MAX_VALUE: left.peekFirst()[0];
                long x2 = right.isEmpty()? Long.MAX_VALUE: right.peekFirst()[0];
                int x = 0;
                if(x1 < x2) {
                    int[] temp = left.pollFirst();
                    x = temp[0];
                    leftH = temp[1];
                } else if(x1 > x2) {
                    int[] temp = right.pollFirst();
                    x = temp[0];
                    rightH = temp[1];
                } else {
                    x = left.peekFirst()[0];
                    leftH = left.pollFirst()[1];
                    rightH = right.pollFirst()[1];
                }
                int h = Math.max(leftH, rightH);
                if(res.isEmpty() || h != res.peekLast()[1]) {
                    res.add(new int[]{x, h});
                }
            }
            return res;
        }
    }
    

  • 1
    S

    How isn't anyone noticing and upvoting this solution???


  • 0
    J

    Nice and clean divide and conquer solution.

    But cannot pass the test [[1,2,1],[2147483646,2147483647,2147483647]].
    Because if x1 == x2 == Integer.MAX_VALUE, maybe left or right is empty, and thus it will cause NullPointerException.

    So the else statement should be modified as

    else {
        x = x1;
        leftH = left.isEmpty() ? 0 : left.pollFirst()[1];
        rightH = right.isEmpty() ? 0 : right.pollFirst()[1];
    }
    

  • 0
    Y

    @JieJackyZhang Thank you for your test case. But I have tried it and my code do pass this test case. I think the reason is you may use Integer.MAX_VALUE instead of Long.MAX_VALUE for long x1 = left.isEmpty()? Long.MAX_VALUE: left.peekFirst()[0]. If you use Integer.MAX_VALUE, you may have the problem because x itself may be Integer.MAX_VALUE.


  • 0
    J

    @yzjJosh Yes, you are right. It will not be a problem if you use Long.MAX_VALUE. Thank you.


Log in to reply
 

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