C++ solution, hashmap and recursion


  • 0
    W

    class Excel {
    private:
    vector<int> board; // change the 2D excel board to 1D vector
    // position x in board -> (a map of {position y in boad, z times})
    // x appears in the sum of y z times. In the problem example: Sum(3, "C", ["A1", "A1:B2"]), x could be A1, y is C3, z is 2 becasue A1 appears twice in sum at 3C.
    unordered_map<int, unordered_map<int, int>> mp;

    int len; // Width of the board
    
    // get {row, column} from a string e.g. "A1"
    pair<int, int> getPair(string s){
        char c = s[0];
        int C = c - 'A';
        int R = stoi( s.substr(1) )-1;
        return {R, C};
    }
    
    // populate the change in position x to position y, e.g. populate the change in A1 to C3
    void populate(int pos, int newval, int oldval){
        if(!mp.count(pos)) return;
        for(auto &p : mp[pos]){
            int oldv = board[p.first];
            board[p.first] += p.second * (newval - oldval);
            populate(p.first, board[p.first], oldv); // recursion
        }
    }
    

    public:
    Excel(int H, char W) {
    int w = W - 'A' + 1;
    board.resize(H * w);
    mp.clear();
    len = w;
    }

    void set(int r, char c, int v) {
        int R = r - 1;
        int C = c - 'A';
        int pos = R * len + C;
        int oldval = board[pos];
        
        // this position is no longer a sum, so erase if it appears at "y" position at map.
        for(auto &p : mp){
            if(p.second.count(pos)) p.second.erase(pos);
        }
        
        // populate the changes.
        populate(pos, v, oldval);
        board[pos] = v; 
    }
    
    int get(int r, char c) {
        int R = r - 1;
        int C = c - 'A';
        return board[R * len + C];        
    }
    
    int sum(int r, char c, vector<string> strs) {
        int R = r - 1;
        int C = c - 'A';
        int pos = R * len + C;
        int oldval = board[pos];
        
         // the contents of sum changes, so erase if it appears at "y" position at map.
        for(auto &p : mp){
            if(p.second.count(pos)) p.second.erase(pos);
        }
        
        
        int sum = 0;
        for(auto str : strs){
            int idx = str.find_first_of(':');
            // single position
            if(idx == -1){
                pair<int, int> coord = getPair(str); 
                int x = coord.first * len + coord.second;
                sum += board[x];
                mp[x][pos] += 1; // update the map, x (A1) now belongs to the sum of pos (C3)
            // range positions
            } else {
                pair<int, int> coord1 = getPair(str.substr(0, idx)); 
                pair<int, int> coord2 = getPair(str.substr(idx+1));
                for(int i = coord1.first; i <= coord2.first; i++){
                    for(int j=coord1.second; j <= coord2.second; j++){
                        int x = i * len + j;
                        sum += board[x];
                        mp[x][pos] += 1;
                    }
                }
            }
        }
        
        board[pos] = sum;
        populate(pos, sum, oldval); // populate the change in pos
        
        return sum;
    }
    

    };

    /**

    • Your Excel object will be instantiated and called as such:
    • Excel obj = new Excel(H, W);
    • obj.set(r,c,v);
    • int param_2 = obj.get(r,c);
    • int param_3 = obj.sum(r,c,strs);
      */

Log in to reply
 

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