C++ easy 12 lines O(n^2) solution


  • 0
    M

    There is no need for HashMap here. It can run faster if we use vector.

        vector<int> fallingSquares(vector<pair<int, int>>& positions) {
            vector<int> res(positions.size(), 0);
            unordered_map<int, vector<int>> pos;
            for(int i=0;i<positions.size();i++) {
                int h=0, s=positions[i].first, e=s+positions[i].second-1;
                for(unordered_map<int, vector<int>>::iterator p=pos.begin();p!=pos.end();p++) {
                    if(p->first>e||p->second[0]<s) continue;
                    h=max(h, p->second[1]);
                }
                pos[s]={e, h+positions[i].second};
                if(i==0) res[i]=positions[i].second;
                else res[i]=max(res[i-1], h+positions[i].second);
            }
            return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.