If you don't know segment trees or facing difficulty in understanding the solutions!
Being not very comfortable with advanced algorithms, I just tried to optimise my brute force solution by a method which is apparantly called \'Coordinate Compre
Being not very comfortable with advanced algorithms, I just tried to optimise my brute force solution by a method which is apparantly called \'Coordinate Compression\'. This solution beats 58% of submissions. Of course, there are better methods which works in O(n log(n)) but this solution would be a decent start if you are at beginner/intermediate level.\n\nI realised that only coordinates that affect my answer are the left and right ends (in x-axis) of the square. So, I tried to capture those end points uniquely and in ascending order using a set. Then I created a reference map which maps original point to the compressed point. Now, we are good to go. Find the maximum height in left to right limits, update the values in this range and save the value to ans array. \n\nHere\'s the code:\n\n```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& positions) {\n        unordered_map<int,int> ref;\n        unordered_map<int,int> m; //index, max height\n        set<int> s;\n        \n        for(int i = 0; i<positions.size(); i++){\n            s.insert(positions[i][0]);    //left end\n            s.insert(positions[i][0]+positions[i][1]-1);    //right end\n        }\n        \n        int mappedValue = 1;\n        for(int originalValue : s){\n            ref.insert({originalValue, mappedValue});\n            mappedValue++;\n        }\n        \n        vector<int> ans(positions.size());\n        int mx = 0;\n        \n        for(int i = 0; i<positions.size(); i++){\n            int left = ref[positions[i][0]];\n            int right = ref[positions[i][0]+positions[i][1]-1];\n            int len = positions[i][1];\n            int prevMax = 0;\n            \n            for(int j = left; j<=right; j++){\n                prevMax = max(prevMax, m[j]);\n            }\n            \n            for(int j = left; j<=right; j++){\n                m[j] = prevMax+len;\n            }\n            \n            mx = max(mx, prevMax+len);\n            ans[i] = mx;\n        }\n        \n        return ans;\n    }\n};\n```
['C']