Java - keep it simple, beats 99.6%
So we have N squares, 2N end points, 2N-1 intervals. We want to update the heights of intervals covered by a new square. Intervals are fixed; no insertion, merg
So we have N squares, 2N end points, 2N-1 intervals. We want to update the heights of intervals covered by a new square. Intervals are fixed; no insertion, merging etc. Sort and binary-search.\n\n```\n    public List<Integer> fallingSquares(int[][] positions)\n    {\n        int[] ends = new int[positions.length*2];\n        for(int i=0; i<positions.length; i++)\n        {\n            ends[i*2+0] = positions[i][0];\n            ends[i*2+1] = positions[i][0]+positions[i][1];\n        }\n        Arrays.sort(ends);\n\n        int[] ceilings = new int[ends.length-1];\n        int maxAll = 0;\n        ArrayList<Integer> results = new ArrayList<>();\n        for(int i=0; i<positions.length; i++)\n        {\n            int X = positions[i][0];\n            int x = Arrays.binarySearch(ends, X);\n            assert x>=0;\n            int maxCeiling = 0;\n            int Y = X + positions[i][1];\n            for(int y=x; ends[y]<Y; y++)\n                maxCeiling = Math.max(maxCeiling, ceilings[y]);\n            maxCeiling += (Y-X);\n            for(int y=x; ends[y]<Y; y++)\n                ceilings[y] = maxCeiling;\n            maxAll = Math.max(maxAll, maxCeiling);\n            results.add(maxAll);\n        }\n        return results;\n    }\n```
[]