Java || 5ms 100% || Fast. Use only arrays for compress and fall
Algorithm:\n1. Gather all of the left and right edge positions for all squares.  For each edge position, save: the original x-position, the index into the posit
**Algorithm:**\n1. **Gather** all of the left and right edge positions for all squares.  For each edge position, save: the original x-position, the index into the `positions[][]` array for that square, and whether the saved position is a left or right edge of the square.\n2. **Sort** all the saved edge positions, which include original array index of the square, and whether the edge position is the left or right edge of a square.\n3. **Compress** the saved and sorted positions to new x-axis values, so that all possible new x-axis values are always at the left or right edge of a block.  Calling them "blocks" now because after x-axis compression, they are no longer "squares".  Since there is a maximum of 1000 squares, there will be a maximum of 2000 compressed positions, so all of the compressed positions can fit in a reasonable sized array.\n4. **Drop** the blocks in order.  Use an array to represent all possible compressed x-axis positions, where the array contains the maximum height of blocks above each compressed position.  For each block, search all x-axis compressed positions used by the block, to find what height the dropped block lands on.  Then update the x-axis compressed positions for the block, to the top of the block after it lands.  Save highest block after dropping each block.\n5. **Return** list of max heights after each dropped block.\n\n**---- Slower code but better programming practices ----**\nRuntimes of 9ms to 11ms,  May 2024.\n```\nclass Solution {\n    class SortPoint {\n        int origPos;\n        short index;\n        boolean isRight;\n        SortPoint(int origPos, int index, boolean isRight) {\n            this.origPos = origPos;\n            this.index = (short)index;\n            this.isRight = isRight;\n        }\n    }\n    \n    public List<Integer> fallingSquares(int[][] positions) {\n        int n = positions.length;\n\n        // Gather all the edge-points from all of the squares, so we \n        // can compress the left and right positions of the square \n        // down into a more manageable range.  \n        final SortPoint[] points = new SortPoint[n * 2];\n        int pointsIdx = 0;\n        for (int i = 0; i < n; i++) {\n            int[] square = positions[i];\n            points[pointsIdx++] = new SortPoint(square[0], i, false);\n            points[pointsIdx++] = new SortPoint(square[0] + square[1], i, true);\n        }\n        \n        // Sort all the squares\' edge points in ascending position \n        // order.\n        Arrays.sort(points, (a, b) -> a.origPos - b.origPos);\n        \n        // Convert the sorted edge points to new compressed position \n        // values.  If adjacent sorted points have the same original \n        // position values, then they are at the same new compressed \n        // positions.  Save the new left and right edge compressed \n        // positions for each square.\n        int newPos = -1;\n        final int[] lefts = new int[n];        \n        final int[] rights = new int[n];\n        int prevPos = -1;\n        for (SortPoint point : points) {\n            if (point.origPos != prevPos) {\n                newPos++;\n                prevPos = point.origPos;\n            }\n            if (point.isRight)\n                rights[point.index] = newPos;\n            else\n                lefts[point.index] = newPos;\n        }\n\n        // With the new compressed left and right edge positions for the \n        // squares, loop to drop each square.  For the new compressed \n        // positions that are within the square, add the height of the square \n        // to all of those x-axis positions, collecting any new highest values.\n        int maxHeight = 0;\n        final int[] xAxis = new int[newPos];\n        List<Integer> result = new ArrayList(n);\n        for (int i = 0; i < n; i++) {       // Drop the boxes in order.\n            int height = 0;\n            for (int start = lefts[i], j = rights[i] - start; j > 0; j--)\n                height = Math.max(height, xAxis[start++]);\n            height += positions[i][1];\n            maxHeight = Math.max(maxHeight, height);\n            for (int start = lefts[i], j = rights[i] - start; j > 0; j--)\n                 xAxis[start++] = height;\n            result.add(maxHeight);\n        }\n        \n        return result;\n    }\n}\n```\n**---- Faster code but bad programming practices ----**\nRuntimes of 5ms to 8ms,  May 2024.\n```\nclass Solution {\n    private static final int ORG_POS_SHIFT = 16;\n    private static final int ORG_POS_MASK = 0xFFF_FFFF;\n    private static final int IS_RIGHT_SHIFT = 12;\n    private static final int IS_RIGHT_MASK = 0xF;\n    private static final int IS_RIGHT = 1 << IS_RIGHT_SHIFT;\n    private static final int IDX_SHIFT = 0;\n    private static final int IDX_MASK = 0xFFF;\n    \n    public List<Integer> fallingSquares(int[][] positions) {\n        int n = positions.length;\n\n        // Gather all the edge-points from all of the squares, so we \n        // can compress the left and right positions of the square \n        // down into a more manageable range.  The edge points of the \n        // square are packed into the bits of a long, so the long \n        // contains: 1) the original position in the most significant \n        // bits so it will eventually be sorted by the original position, \n        // 2) a boolean indicating if this position is for the right \n        // edge of the square, and 3) the original index of the \n        // square in the positions[] array.\n        final long[] points = new long[n * 2];\n        int pointsIdx = 0;\n        for (int i = 0; i < n; i++) {\n            int[] square = positions[i];\n            points[pointsIdx++] = ((long)square[0] << ORG_POS_SHIFT) | i;\n            points[pointsIdx++] = (((long)square[0] + square[1]) << ORG_POS_SHIFT) | \n                                    i | IS_RIGHT;\n        }\n        \n        // Sort all the squares\' edge points in ascending position \n        // order.\n        Arrays.sort(points);\n        \n        // Convert the sorted edge points to new compressed position \n        // values.  If adjacent sorted points have the same original \n        // position values, then they are at the same new compressed \n        // positions.  Save the new left and right edge compressed \n        // positions for each square.\n        int newPos = -1;\n        final int[] lefts = new int[n];        \n        final int[] rights = new int[n];\n        long endNewPos = -1;\n        for (long point : points) {\n            if (point > endNewPos) {\n                newPos++;\n                endNewPos = point | IS_RIGHT | IDX_MASK;\n            }\n            if ((point & IS_RIGHT) != 0)\n                rights[(int)point & IDX_MASK] = newPos;\n            else\n                lefts[(int)point & IDX_MASK] = newPos;\n        }\n\n        // With the new compressed left and right edge positions for the \n        // squares, loop to drop each square.  For the new compressed \n        // positions that are within the square, add the height of the square \n        // to all of those x-axis positions, collecting any new highest values.\n        int maxHeight = 0;\n        final int[] xAxis = new int[newPos];\n        List<Integer> result = new ArrayList(n);\n        for (int i = 0; i < n; i++) {       // Drop the boxes in succession \n            int height = 0;\n            for (int start = lefts[i], j = rights[i] - start; j > 0; j--)\n                height = Math.max(height, xAxis[start++]);\n            height += positions[i][1];\n            maxHeight = Math.max(maxHeight, height);\n            for (int start = lefts[i], j = rights[i] - start; j > 0; j--)\n                 xAxis[start++] = height;\n            result.add(maxHeight);\n        }\n        \n        return result;\n    }\n}\n```
['Java']