An initial solution, Java O(n^2), beat 95%


  • 0

    The solution uses similar idea as in Google's skyline problem.

    class Solution {
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> res = new ArrayList<>();
            if (positions == null || positions.length == 0) return res;
            List<Point> skyLine = new ArrayList<>();
            // Setup
            skyLine.add(new Point(positions[0][0], positions[0][1]));
            skyLine.add(new Point(positions[0][0] + positions[0][1], 0));
            int maxHeight = positions[0][1];
            int height = 0;
            res.add(maxHeight);
            for (int i = 1; i < positions.length; i++) {
                int startPosition = positions[i][0];
                int endPosition = positions[i][0] + positions[i][1];
                int start = binarySearch(skyLine, startPosition);
                height = start == -1 ? 0 : skyLine.get(start).y;
                for (int j = start + 1; j < skyLine.size(); j++) {
                    if (skyLine.get(j).x >= endPosition) break;
                    height = Math.max(height, skyLine.get(j).y);
                }
                height += positions[i][1];
                // clean up
                int index = start + 1;
                int endHeight = start == -1 ? 0 : skyLine.get(start).y;
                while (index < skyLine.size() && skyLine.get(index).x < endPosition) {
                    endHeight = skyLine.get(index).y;
                    skyLine.remove(index);
                }
                int startIndex = -1;
                if (start != -1 && skyLine.get(start).x == positions[i][0]) {
                    skyLine.get(start).y = height;
                    startIndex = start;
                } else {
                    startIndex = start + 1;
                    skyLine.add(startIndex, new Point(positions[i][0], height));
                }
                if (startIndex + 1 < skyLine.size() && skyLine.get(startIndex + 1).x == endPosition) {
                    // do nothing
                } else {
                    skyLine.add(startIndex + 1, new Point(endPosition, endHeight));
                }
                maxHeight = Math.max(height, maxHeight);
                res.add(maxHeight);
                //for (Point p : skyLine) System.out.print(p + " # ");
                //System.out.println();
            }
            return res;
        }
        
        private int binarySearch(List<Point> nums, int target) {
            int lo = 0, hi = nums.size() - 1;
            while (lo <= hi) {
                int mid = (lo + hi) >>> 1;
                if (nums.get(mid).x > target) hi = mid - 1;
                else lo = mid + 1;
            }
            return hi;
        }
        
        public static class Point {
            int x;
            int y;
            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
            @Override
            public String toString() {
                return x + " " + y;
            }
        }
    }
    

Log in to reply
 

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