C++ Clean Solution | Easy O(N^2)
Approach\n\nThe idea is that when we are putting the $i$-th square, we need to know the "highest" square that it will be put into.\n\nLet $h[i]$ be the height o
# Approach\n\nThe idea is that when we are putting the $i$-th square, we need to know the "highest" square that it will be put into.\n\nLet $h[i]$ be the height of putting the $i$-th square, then initially $h[i]=p[i][1]$ which is the size of the square.\n\nNow we can find all $j < i$ such that $i-$th square overlaps with the $j$-th square, we will need to find the maximal $h[j]$\n\nNow $h[i]=\\max(h[i], h[j]+p[i][1)$ if we have found $j$\n\nWe can store the answer by keeping track of the maximal $h[i]$ from left to right. \n\n# Complexity\n- Time complexity: $O(N^2)$\n\n- Space complexity: $O(N)$\n\n## Note\n- There\'s a more optimal solution with $O(N \\log N)$ using Segment Tree Lazy Propagation\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& p) {\n        int n = (int) p.size();\n        vector<int> ans(n);\n        vector<int> h(n);\n        int res = 0;\n        for (int i = 0; i < n; i++) {\n            h[i] = p[i][1];\n            for (int j = 0; j < i; j++) {\n                int li = p[i][0];\n                int ri = li + p[i][1];\n                int lj = p[j][0];\n                int rj = lj + p[j][1];\n                if (li >= lj) {\n                    swap(li, lj);\n                    swap(ri, rj);\n                }\n                if (li <= lj && lj < ri) {\n                    h[i] = max(h[i], h[j] + p[i][1]);\n                }\n            }\n            res = max(res, h[i]);\n            ans[i] = res;\n        }\n        return ans;\n    }\n};\n```
['C++']