# C++ solution, hashmap and recursion

• 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);
*/

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