C++ | segment tree | lazy propagations | O(n^2) |O(nlogn) | solution with Explanation
So, here the heightOfSquare[i] will be max(heightOfSquare[j] where j < i and that are overlap with square[i] via x coordinate) + sideLength[i] (i.e. positions[i
So, here the **heightOfSquare**[i] will be **max**(**heightOfSquare**[j] where j < i and that are overlap with **square**[i] via x coordinate) + **sideLength**[i] (i.e. **positions**[i][1]).\n\nBut, **results**[i] will be **max**(**prefixResult**,**heightOfSquare**[i]) because it may happen that tallest square is not i it\'s j where j < i.\n\n***Overlapping Conditions** :*\nleft and right point of ith box should be as follow ...\nleft(l) should be **positions**[i][0] (that given)\nright(r) should be **positions**[i][0] + **positions**[i][1] - **1** \nwe take  **-1** because problem statement say that (A square brushing the left/right side of another square does not count as landing on it).\n\nyou can also take left and right points as  (**positions**[i][0]+1) and (**positions**[i][0] + **positions**[i][1]) respectively.\n\nAs we know that a square box **i** placed top of another square **j** if and only if **(li-ri)** and **(lj-rj)** are overlap where, **li,ri** means left and right point of square **i**.\n \n1.  li <= rj <= ri\n2.  li <= lj <= ri\n3.  li <= rj <= ri\n4.  li <= lj <= ri\nIf any of the above condition is true then we can say that square_i(li-ri) and square_j(lj-rj) are ovelaps.\n```\nBrute Force Approach:\nvector<int> fallingSquares(vector<vector<int>>& positions) {\n        vector<int>results;\n        int n = (int)positions.size();\n        auto check_overlap =[&](int i,int j){\n            int li = positions[i][0];\n            int ri = positions[i][0] + positions[i][1] - 1;\n            int lj = positions[j][0];\n            int rj = positions[j][0] + positions[j][1] - 1;    \n            return ((li <= lj && lj <= ri) or (li <= rj && rj <= ri) or (lj <= li && li <= rj) or (lj <= ri && ri <= rj));\n        };\n        \n        vector<int>heightOfSquare(n,0);\n        \n        int prefixResult = 0;\n        \n        for(int i = 0; i < n; ++i){\n            \n            int sideLength = positions[i][1];\n            int mxHeight = 0;        \n            for(int j = 0; j < i; ++j){\n                if(check_overlap(i,j))\n                    mxHeight = max(mxHeight , heightOfSquare[j]);\n            }\n            \n            heightOfSquare[i] = mxHeight + sideLength;\n            \n            prefixResult = max(prefixResult,heightOfSquare[i]);\n            \n            results.push_back(prefixResult);\n\n        }\n        return results;\n\t}\n\tTime : O(N^2)\n\tSpace : O(N)\n```\n\nNow we have to optimize this solution using lazy propagation and Co-ordinate compression technique.\n```\n//  a = max(a,b);\nvoid umax(int &a,int b){\n    a = max(a,b);\n}\nclass LaZy{\n    vector<int>lazy,tree,a;\npublic:\n    LaZy(int n){\n//         initialization\n        lazy.assign(4*n,0);\n        tree.assign(4*n,0);\n    }\n\n//  update lazy\n    void push(int nd,int ss,int se){\n        int x = lazy[nd];\n//      lazy value update   \n        if(x){\n            umax(tree[nd],x);\n            lazy[nd] = 0;\n        }\n//      not leaf node and lazy value of parent node updated\n        if(ss != se and x){\n            umax(lazy[2*nd],x);\n            umax(lazy[2*nd+1],x);\n        }\n    }\n//  update range (l,r) such that arr[i] = max(arr[i],val) for l <= i<= r.\n    void update(int nd,int ss,int se,int l,int r,int val)\n    {\n        push(nd,ss,se);\n        if(ss > r or se < l)\n            return ;\n        if(l <= ss and se <= r)\n        {\n            umax(lazy[nd],val);\n            push(nd,ss,se); \n            return;\n        }\n        int mid = (ss+se)/2;\n//      call for left tree\n        update(2*nd,ss,mid,l,r,val);\n//      call for right tree\n        update(2*nd+1,mid+1,se,l,r,val);\n//      update current node value from it\'s subtree values.   \n        tree[nd] = max(tree[2*nd],tree[2*nd+1]);\n    }\n    \n//  find maximum element in range(l,r) i.e. mx = max({arr[l],arr[l+1],arr[l+2]....arr[r]})    \n    int query(int nd,int ss,int se,int l,int r)\n    {\n        \n        push(nd,ss,se);\n        if(ss > r or se < l)\n            return 0;\n        if(l <= ss and se <= r){\n            return tree[nd];\n        }\n        int mid = (ss+se)/2;   \n        return max(query(2*nd,ss,mid,l,r),query(2*nd+1,mid+1,se,l,r));\n    }\n};\n\n\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& positions) {\n\n // Now, as we can see that coordinate ranges is too large(10^8 + 10^6 + 1) that not fit in general array.\n// so we have to used coordinate compressions technique.\n        \n\n//      for storing index   \n        unordered_map<int,int>index;\n\n//      storing elements in sorted order   \n        set<int>st;\n        \n//      As we know that a square box i placed top of another square j if and only if (li-ri) and (lj-rj) are overlap.\n        \n//      If ((li <= rj <= ri) or (li <= lj <= ri) or (li <= rj <= ri) or (li <= lj <= ri)) is true then we can see that square_i(li-ri) and square_j(lj-rj) are ovelaps.\n        \n        \n//      so we can see that overlaping only depends on left and right points of the square not entire length of the square.\n        \n        for(int i = 0; i < (int)positions.size(); ++i){\n            int l = positions[i][0];\n            int r = positions[i][0] + positions[i][1] - 1;\n            st.insert(l);\n            st.insert(r); \n        }\n        \n        \n//      Now, here what I am doing that if the set contain st = {1,7,10,20} then we simple do that index[1] = 1 and index[7] = 2 and so on...\n        \n        int cnt = 0;\n//      itterate over the set   \n        for(auto it : st)\n            index[it] = ++cnt;\n        \n//      now we instantiated LaZy objects lz and passing size of the  index(how many different indices are there).\n        LaZy lz(cnt);\n        \n//      used for storing results.   \n        vector<int>results;\n\n//         \n        int prefixResult = 0;\n        for(int i = 0; i < (int)positions.size(); ++i){\n            int li = positions[i][0];\n            int ri = positions[i][0] + positions[i][1] - 1;\n            \n            int index_li = index[li];\n            int index_ri = index[ri];\n            \n//          Now, we find the square whose some part are in range (li-ri) because those squares are overlapping with current square_i.\n            \n//          so when we dropped square_i then height of the square_i will be max(the height of the square that are in range li-ri) + height of square_i.\n            \n//          so, here you might little bit confused that why I passing index_i and index_ri instead of passing li,ri.\n//          so, the answer will be the value of li,ri are quite large that cann\'t fixed inarray so we passed index_li,index_ri.   \n            \n            int height_i = lz.query(1,1,cnt,index_li,index_ri) + positions[i][1];\n            \n//          so, after placing the square at li-ri the height of the range li-ri will be changes and i.e. height_i.   \n            lz.update(1,1,cnt,index_li,index_ri,height_i);\n\n//          It mights happen that tallest square present ouside of this range li-ri in this actual answer will be max(prefixResult,height_i).\n            \n            umax(prefixResult,height_i);\n            \n//           add results into the vector  \n            results.push_back(prefixResult);\n        }\n        return results;\n    }\n};\nTime : O(nlogn)\nSpace : O(n)\n```\n
[]