Super Simple Java Solution - TreeSet with explanation
The solution is simple as follows:\n1- We need to records 3 things of each square: {start point, end point, current height}\nstart point is given;\nend point is
The solution is simple as follows:\n1- We need to records 3 things of each square: {start point, end point, current height}\nstart point is given;\nend point is : start+end-1;\ncurrent height is: if it lies on any square it will be baseSquareHeight+side_length otherwise it will be side_length\n2- Whenever a new square drops we need to find the highest dropped square which has some base in common with the new square. It is similar to finding two rectangle with common area. So the formula is:\nMath.max(new square start, dropped square start)<=Math.min(new square end, dropped square end)\n3- In case we have multiple dropped squares which have common area with the new square, choose the one with highest height.\n4- Then record the new square, and its height (if it lies on any square it will be baseSquareHeight+side_length otherwise it will be side_length)\n```\npublic List<Integer> fallingSquares(int[][] positions) { \n\t TreeSet<int[]> squares = new TreeSet<>(new Comparator<int[]>(){\n\t\t public int compare(int[] sqr1, int[] sqr2){\n\t\t\t return -(sqr1[2]-sqr2[2]); //highest squares at first\n\t\t }\n\t });\n\t List<Integer> result = new ArrayList<>();\n\t int maxHeight=-1;\n\t for(int[] position:positions){\n\t\t int start=position[0]; int end=position[0]+position[1]-1;\n\t\t int height=0;\n\t\t for(int[] square:squares){\n\t\t //find if the new square lies on any dropped square. If yes, pick the highest one\n\t\t\t if(Math.max(start, square[0])<=Math.min(end, square[1]) && height<square[2]) {height=square[2]; break;}\n\t\t }\n\t\t height+=position[1]; //baseSquareHeight+side_length\n\t\t maxHeight=Math.max(maxHeight, height);\n\t\t squares.add(new int[]{start,end,height});\n\t\t result.add(maxHeight);\n\t }\n\t \n    return result;\n }\n```
[]