The "Design Excel Sum Formula" problem asks you to implement a simplified version of an Excel spreadsheet. Specifically, you need to support the following operations for a table of size H x W (height and width):
set(r, c, val): Set the value of the cell at row r and column c to val.get(r, c): Return the current value of the cell at row r and column c.sum(r, c, strs): Set the cell at (r, c) to be the sum of the cells/ranges described by strs. Each string in strs can be a single cell (like "A1") or a rectangular range (like "A1:B2"). If a cell is set to a sum, its value must update automatically when any of the referenced cells change.You must maintain dependencies so that sum formulas update dynamically, just like in Excel. The key constraints are:
The challenge is to support both direct value assignments and dynamic sum formulas, while ensuring changes propagate through all dependent cells. At first glance, a brute-force approach might seem possible: whenever a sum is set, compute the sum and store it. However, if a referenced cell changes, all formulas depending on it must also update, potentially leading to inefficient recalculations.
To optimize, we need to track dependencies between cells—essentially building a graph where each cell knows which other cells depend on it. This way, when a cell's value changes, we can efficiently propagate updates only to affected cells. This is similar to how spreadsheets like Excel manage formulas and dependencies.
The main conceptual shift is from recalculating everything on each change to smartly propagating changes using dependency tracking, minimizing redundant work and ensuring correctness.
set or because a referenced cell changed), we recursively update all cells that depend on it.This approach ensures that updates are efficient and only affect relevant cells, similar to how real spreadsheet software handles cell formulas and dependencies.
Consider a 3x3 spreadsheet (rows 1-3, columns A-C). Let's walk through these operations:
set(1, "A", 5) sets cell A1 to 5.set(1, "B", 3) sets cell B1 to 3.sum(1, "C", ["A1", "B1"]) sets C1 to the sum of A1 and B1 (5 + 3 = 8).get(1, "C") returns 8.set(1, "A", 10) updates A1 to 10. Since C1 depends on A1, C1 is updated to 10 + 3 = 13.get(1, "C") now returns 13.Note how updating A1 automatically causes C1 to update, because C1's formula tracks dependencies on A1 and B1.
The optimized approach is much more scalable, especially for large spreadsheets with many formulas.
The "Design Excel Sum Formula" problem is a classic example of dependency management, similar to how spreadsheets handle formulas. The key insight is to track dependencies between cells so that updates propagate efficiently and automatically. By representing formulas, values, and dependencies explicitly, we ensure correctness and performance. This approach mirrors real-world spreadsheet engines and teaches valuable lessons about graphs, propagation, and efficient data structures.
class Excel:
def __init__(self, H: int, W: str):
self.H = H
self.W = ord(W) - ord('A') + 1
self.cells = [[{'val': 0, 'formula': None} for _ in range(self.W)] for _ in range(self.H)]
self.dependents = [[set() for _ in range(self.W)] for _ in range(self.H)]
self.depends_on = [[set() for _ in range(self.W)] for _ in range(self.H)]
def _parse_ref(self, ref):
col = ord(ref[0]) - ord('A')
row = int(ref[1:]) - 1
return row, col
def _expand_refs(self, strs):
refs = []
for s in strs:
if ':' in s:
start, end = s.split(':')
r1, c1 = self._parse_ref(start)
r2, c2 = self._parse_ref(end)
for i in range(min(r1, r2), max(r1, r2)+1):
for j in range(min(c1, c2), max(c1, c2)+1):
refs.append((i, j))
else:
refs.append(self._parse_ref(s))
return refs
def set(self, r: int, c: str, v: int) -> None:
row, col = r-1, ord(c)-ord('A')
# Remove old dependencies if any
if self.cells[row][col]['formula'] is not None:
for dep in self.depends_on[row][col]:
self.dependents[dep[0]][dep[1]].discard((row, col))
self.depends_on[row][col] = set()
self.cells[row][col]['formula'] = None
self.cells[row][col]['val'] = v
self._propagate(row, col)
def get(self, r: int, c: str) -> int:
row, col = r-1, ord(c)-ord('A')
return self.cells[row][col]['val']
def sum(self, r: int, c: str, strs: [str]) -> int:
row, col = r-1, ord(c)-ord('A')
refs = self._expand_refs(strs)
# Remove old dependencies if any
if self.cells[row][col]['formula'] is not None:
for dep in self.depends_on[row][col]:
self.dependents[dep[0]][dep[1]].discard((row, col))
self.depends_on[row][col] = set(refs)
for dep in refs:
self.dependents[dep[0]][dep[1]].add((row, col))
self.cells[row][col]['formula'] = list(refs)
self.cells[row][col]['val'] = sum(self.cells[i][j]['val'] for (i, j) in refs)
self._propagate(row, col)
return self.cells[row][col]['val']
def _propagate(self, row, col):
# Recompute all dependents recursively
for dep in self.dependents[row][col]:
refs = self.cells[dep[0]][dep[1]]['formula']
if refs is not None:
self.cells[dep[0]][dep[1]]['val'] = sum(self.cells[i][j]['val'] for (i, j) in refs)
self._propagate(dep[0], dep[1])
class Excel {
public:
int H, W;
struct Cell {
int val = 0;
vector<pair<int, int>> formula;
};
vector<vector<Cell>> cells;
vector<vector<set<pair<int, int>>>> dependents;
vector<vector<set<pair<int, int>>>> depends_on;
Excel(int height, char width) {
H = height;
W = width - 'A' + 1;
cells = vector<vector<Cell>>(H, vector<Cell>(W));
dependents = vector<vector<set<pair<int, int>>>>(H, vector<set<pair<int, int>>>(W));
depends_on = vector<vector<set<pair<int, int>>>>(H, vector<set<pair<int, int>>>(W));
}
pair<int, int> parse_ref(const string& ref) {
int col = ref[0] - 'A';
int row = stoi(ref.substr(1)) - 1;
return {row, col};
}
vector<pair<int, int>> expand_refs(const vector<string>& strs) {
vector<pair<int, int>> refs;
for (const auto& s : strs) {
auto pos = s.find(':');
if (pos != string::npos) {
auto start = parse_ref(s.substr(0, pos));
auto end = parse_ref(s.substr(pos+1));
for (int i = min(start.first, end.first); i <= max(start.first, end.first); ++i) {
for (int j = min(start.second, end.second); j <= max(start.second, end.second); ++j) {
refs.emplace_back(i, j);
}
}
} else {
refs.push_back(parse_ref(s));
}
}
return refs;
}
void set(int r, char c, int v) {
int row = r - 1, col = c - 'A';
// Remove old dependencies
if (!cells[row][col].formula.empty()) {
for (auto& dep : depends_on[row][col]) {
dependents[dep.first][dep.second].erase({row, col});
}
depends_on[row][col].clear();
cells[row][col].formula.clear();
}
cells[row][col].val = v;
propagate(row, col);
}
int get(int r, char c) {
int row = r - 1, col = c - 'A';
return cells[row][col].val;
}
int sum(int r, char c, vector<string> strs) {
int row = r - 1, col = c - 'A';
auto refs = expand_refs(strs);
// Remove old dependencies
if (!cells[row][col].formula.empty()) {
for (auto& dep : depends_on[row][col]) {
dependents[dep.first][dep.second].erase({row, col});
}
}
depends_on[row][col] = set<pair<int, int>>(refs.begin(), refs.end());
for (auto& dep : refs) {
dependents[dep.first][dep.second].insert({row, col});
}
cells[row][col].formula = refs;
int s = 0;
for (auto& p : refs) s += cells[p.first][p.second].val;
cells[row][col].val = s;
propagate(row, col);
return s;
}
void propagate(int row, int col) {
for (auto& dep : dependents[row][col]) {
auto& refs = cells[dep.first][dep.second].formula;
if (!refs.empty()) {
int s = 0;
for (auto& p : refs) s += cells[p.first][p.second].val;
cells[dep.first][dep.second].val = s;
propagate(dep.first, dep.second);
}
}
}
};
import java.util.*;
class Excel {
int H, W;
Cell[][] cells;
Set<int[]>[][] dependents;
Set<int[]>[][] dependsOn;
static class Cell {
int val = 0;
List<int[]> formula = null;
}
public Excel(int height, char width) {
H = height;
W = width - 'A' + 1;
cells = new Cell[H][W];
dependents = new HashSet[H][W];
dependsOn = new HashSet[H][W];
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cells[i][j] = new Cell();
dependents[i][j] = new HashSet<>();
dependsOn[i][j] = new HashSet<>();
}
}
}
private int[] parseRef(String ref) {
int col = ref.charAt(0) - 'A';
int row = Integer.parseInt(ref.substring(1)) - 1;
return new int[]{row, col};
}
private List<int[]> expandRefs(List<String> strs) {
List<int[]> refs = new ArrayList<>();
for (String s : strs) {
if (s.contains(":")) {
String[] parts = s.split(":");
int[] start = parseRef(parts[0]);
int[] end = parseRef(parts[1]);
for (int i = Math.min(start[0], end[0]); i <= Math.max(start[0], end[0]); ++i) {
for (int j = Math.min(start[1], end[1]); j <= Math.max(start[1], end[1]); ++j) {
refs.add(new int[]{i, j});
}
}
} else {
refs.add(parseRef(s));
}
}
return refs;
}
public void set(int r, char c, int v) {
int row = r - 1, col = c - 'A';
// Remove old dependencies
if (cells[row][col].formula != null) {
for (int[] dep : dependsOn[row][col]) {
dependents[dep[0]][dep[1]].removeIf(x -> x[0] == row && x[1] == col);
}
dependsOn[row][col].clear();
cells[row][col].formula = null;
}
cells[row][col].val = v;
propagate(row, col);
}
public int get(int r, char c) {
int row = r - 1, col = c - 'A';
return cells[row][col].val;
}
public int sum(int r, char c, List<String> strs) {
int row = r - 1, col = c - 'A';
List<int[]> refs = expandRefs(strs);
// Remove old dependencies
if (cells[row][col].formula != null) {
for (int[] dep : dependsOn[row][col]) {
dependents[dep[0]][dep[1]].removeIf(x -> x[0] == row && x[1] == col);
}
}
dependsOn[row][col] = new HashSet<>();
for (int[] dep : refs) {
dependsOn[row][col].add(dep);
dependents[dep[0]][dep[1]].add(new int[]{row, col});
}
cells[row][col].formula = refs;
int s = 0;
for (int[] p : refs) s += cells[p[0]][p[1]].val;
cells[row][col].val = s;
propagate(row, col);
return s;
}
private void propagate(int row, int col) {
for (int[] dep : dependents[row][col]) {
List<int[]> refs = cells[dep[0]][dep[1]].formula;
if (refs != null) {
int s = 0;
for (int[] p : refs) s += cells[p[0]][p[1]].val;
cells[dep[0]][dep[1]].val = s;
propagate(dep[0], dep[1]);
}
}
}
}
class Excel {
constructor(H, W) {
this.H = H;
this.W = W.charCodeAt(0) - 'A'.charCodeAt(0) + 1;
this.cells = Array.from({length: H}, () => Array.from({length: this.W}, () => ({val: 0, formula: null})));
this.dependents = Array.from({length: H}, () => Array.from({length: this.W}, () => new Set()));
this.dependsOn = Array.from({length: H}, () => Array.from({length: this.W}, () => new Set()));
}
_parseRef(ref) {
let col = ref.charCodeAt(0) - 'A'.charCodeAt(0);
let row = parseInt(ref.slice(1)) - 1;
return [row, col];
}
_expandRefs(strs) {
let refs = [];
for (let s of strs) {
if (s.includes(":")) {
let [start, end] = s.split(":");
let [r1, c1] = this._parseRef(start);
let [r2, c2] = this._parseRef(end);
for (let i = Math.min(r1, r2); i <= Math.max(r1, r2); ++i) {
for (let j = Math.min(c1, c2); j <= Math.max(c1, c2); ++j) {
refs.push([i, j]);
}
}
} else {
refs.push(this._parseRef(s));
}
}
return refs;
}
set(r, c, v) {
let row = r - 1, col = c.charCodeAt(0) - 'A'.charCodeAt(0);
// Remove old dependencies
if (this.cells[row][col].formula !== null) {
for (let dep of this.dependsOn[row][col]) {
this.dependents[dep[0]][dep[1]].delete([row, col]);
}
this.dependsOn[row][col] = new Set();
this.cells[row][col].formula = null;
}
this.cells[row][col].val = v;
this._propagate(row, col);
}
get(r, c) {
let row = r - 1, col = c.charCodeAt(0) - 'A'.charCodeAt(0);
return this.cells[row][col].val;
}
sum(r, c, strs) {
let row = r - 1, col = c.charCodeAt(0) - 'A'.charCodeAt(0);
let refs = this._expandRefs(strs);
// Remove old dependencies
if (this.cells[row][col].formula !== null) {
for (let dep of this.dependsOn[row][col]) {
this.dependents[dep[0]][dep[1]].delete([row, col]);
}
}
this.dependsOn[row][col] = new Set(refs.map(x => x));
for (let dep of refs) {
this.dependents[dep[0]][dep[1]].add([row, col]);
}
this.cells[row][col].formula = refs;
this.cells[row][col].val = refs.reduce((acc, [i, j]) => acc + this.cells[i][j].val, 0);
this._propagate(row, col);
return this.cells[row][col].val;
}
_propagate(row, col) {
for (let dep of this.dependents[row][col]) {
let refs = this.cells[dep[0]][dep[1]].formula;
if (refs !== null) {
this.cells[dep[0]][dep[1]].val = refs.reduce((acc, [i, j]) => acc + this.cells[i][j].val, 0);
this._propagate(dep[0], dep[1]);
}
}
}
}