Design Excel Sum Formula
Design Excel Sum Formula is a hard design data structures problem solved with the dependency graph pattern.
The best approach, optimal (dependency graph with eager updates), runs in O(1) get, O(26² + P) for set and sum time and O(26² · F) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (evaluate formulas on every read) up.
Problem
Build a small spreadsheet class Excel. Excel(int height, char width) creates a sheet with rows 1 to height and columns 'A' to width, where every cell starts at 0.
set(row, column, val) puts the number val into a cell, replacing any formula it held. get(row, column) returns the cell’s current value. sum(row, column, numbers) stores a formula in the cell and returns its value: the cell becomes the total of everything listed in numbers, where each entry is either one cell such as "C2" or a rectangle such as "A1:B3" (from the top-left to the bottom-right cell, inclusive). A cell that is mentioned more than once, directly or through overlapping rectangles, is added once per mention.
A formula stays live: whenever any cell it depends on changes, directly or through other formulas, its value changes too, until the cell is overwritten by set or by another sum.
Examples
Example 1
- Input
Excel(3, 'C'), set(1, 'A', 4), set(2, 'B', 3), sum(3, 'C', ["A1", "A1:B2"]), set(2, 'B', 5), get(3, 'C'), set(1, 'A', 1), get(3, 'C')- Output
11, 13, 7- Why
- C3 = A1 + (A1 + B1 + A2 + B2), so A1 is counted twice: 4 + 4 + 3 = 11. Raising B2 to 5 gives 13; lowering A1 to 1 gives 1 + 1 + 5 = 7.
Example 2
- Input
Excel(2, 'B'), sum(1, 'A', ["B1", "B2"]), set(1, 'B', 2), sum(2, 'A', ["A1", "A1"]), set(1, 'A', 10), get(2, 'A'), set(2, 'B', 7), get(1, 'A')- Output
0, 4, 20, 10- Why
- A2 tracks twice A1. Setting A1 to 10 replaces its formula, so later changes to B2 no longer affect it.
Constraints
1 <= height <= 26and'A' <= width <= 'Z'1 <= row <= heightand'A' <= column <= widthin every call-100 <= val <= 1001 <= numbers.length <= 5; each entry is a cell like"B3"or a range like"A1:C2"whose first cell is the top-left one.- Formulas never create a circular reference, and every value stays within a 32-bit signed integer.
- At most 100 calls in total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (evaluate formulas on every read) | O(1) set, O(26² · F) sum, get up to O(P · 26²) | O(26² · F) |
| Optimal (dependency graph with eager updates) | O(1) get, O(26² + P) for set and sum | O(26² · F) |
1Brute force (evaluate formulas on every read)
O(1) set, O(26² · F) sum, get up to O(P · 26²)Expanding ranges touches at most 26 x 26 cells per entry; a read walks every path P through the formula chain below the cell.O(26² · F)Every formula stores up to 26 x 26 referenced cells; F is the number of formula cells.Store for each cell either a plain value or a formula, kept as a map from referenced cell to how many times it is mentioned. Reading a cell with a formula evaluates it recursively: the sum of each referenced cell's value times its count. Nothing is cached, so every read redoes the work.
set: store the value and delete any formula on the cell.sum: expand every entry ofnumbers(single cells and ranges) into a count map, store it as the cell's formula, and returngetof that cell.get: if the cell has a formula, return the sum ofget(ref) * countover its entries; otherwise return the stored value.
class Excel {
private final int[][] val;
private final Map<Integer, Integer>[][] formula;
@SuppressWarnings("unchecked")
public Excel(int height, char width) {
val = new int[height + 1][width - 'A' + 1];
formula = new HashMap[height + 1][width - 'A' + 1];
}
public void set(int row, char column, int v) {
formula[row][column - 'A'] = null;
val[row][column - 'A'] = v;
}
public int get(int row, char column) {
Map<Integer, Integer> f = formula[row][column - 'A'];
if (f == null) return val[row][column - 'A'];
int total = 0;
for (Map.Entry<Integer, Integer> e : f.entrySet())
total += get(e.getKey() / 26, (char) ('A' + e.getKey() % 26)) * e.getValue();
return total;
}
public int sum(int row, char column, String[] numbers) {
Map<Integer, Integer> f = new HashMap<>();
for (String s : numbers) {
String[] parts = s.split(":");
String last = parts[parts.length - 1];
int r1 = Integer.parseInt(parts[0].substring(1)), c1 = parts[0].charAt(0) - 'A';
int r2 = Integer.parseInt(last.substring(1)), c2 = last.charAt(0) - 'A';
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++) f.merge(r * 26 + c, 1, Integer::sum);
}
formula[row][column - 'A'] = f;
return get(row, column);
}
}class Excel:
def __init__(self, height: int, width: str):
cols = ord(width) - ord("A") + 1
self.val = [[0] * cols for _ in range(height + 1)]
self.formula = [[None] * cols for _ in range(height + 1)]
def set(self, row: int, column: str, val: int) -> None:
c = ord(column) - ord("A")
self.formula[row][c] = None
self.val[row][c] = val
def get(self, row: int, column: str) -> int:
c = ord(column) - ord("A")
f = self.formula[row][c]
if f is None:
return self.val[row][c]
total = 0
for key, cnt in f.items():
total += self.get(key // 26, chr(ord("A") + key % 26)) * cnt
return total
def sum(self, row: int, column: str, numbers: List[str]) -> int:
f = {}
for s in numbers:
parts = s.split(":")
first, last = parts[0], parts[-1]
r1, c1 = int(first[1:]), ord(first[0]) - ord("A")
r2, c2 = int(last[1:]), ord(last[0]) - ord("A")
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
f[r * 26 + c] = f.get(r * 26 + c, 0) + 1
self.formula[row][ord(column) - ord("A")] = f
return self.get(row, column)class Excel {
vector<vector<int>> val;
vector<vector<map<int, int>>> formula;
vector<vector<bool>> hasFormula;
public:
Excel(int height, char width)
: val(height + 1, vector<int>(width - 'A' + 1, 0)),
formula(height + 1, vector<map<int, int>>(width - 'A' + 1)),
hasFormula(height + 1, vector<bool>(width - 'A' + 1, false)) {}
void set(int row, char column, int v) {
hasFormula[row][column - 'A'] = false;
formula[row][column - 'A'].clear();
val[row][column - 'A'] = v;
}
int get(int row, char column) {
if (!hasFormula[row][column - 'A']) return val[row][column - 'A'];
int total = 0;
for (auto& [key, cnt] : formula[row][column - 'A'])
total += get(key / 26, (char)('A' + key % 26)) * cnt;
return total;
}
int sum(int row, char column, vector<string> numbers) {
map<int, int> f;
for (auto& s : numbers) {
size_t colon = s.find(':');
string first = s.substr(0, colon);
string last = colon == string::npos ? first : s.substr(colon + 1);
int r1 = stoi(first.substr(1)), c1 = first[0] - 'A';
int r2 = stoi(last.substr(1)), c2 = last[0] - 'A';
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++) f[r * 26 + c]++;
}
formula[row][column - 'A'] = f;
hasFormula[row][column - 'A'] = true;
return get(row, column);
}
};class Excel {
constructor(height, width) {
const cols = width.charCodeAt(0) - 65 + 1;
this.val = Array.from({ length: height + 1 }, () => new Array(cols).fill(0));
this.formula = Array.from({ length: height + 1 }, () => new Array(cols).fill(null));
}
set(row, column, val) {
const c = column.charCodeAt(0) - 65;
this.formula[row][c] = null;
this.val[row][c] = val;
}
get(row, column) {
const c = column.charCodeAt(0) - 65;
const f = this.formula[row][c];
if (f === null) return this.val[row][c];
let total = 0;
for (const [key, cnt] of f)
total += this.get(Math.floor(key / 26), String.fromCharCode(65 + (key % 26))) * cnt;
return total;
}
sum(row, column, numbers) {
const f = new Map();
for (const s of numbers) {
const parts = s.split(":");
const first = parts[0], last = parts[parts.length - 1];
const r1 = Number(first.slice(1)), c1 = first.charCodeAt(0) - 65;
const r2 = Number(last.slice(1)), c2 = last.charCodeAt(0) - 65;
for (let r = r1; r <= r2; r++)
for (let c = c1; c <= c2; c++) f.set(r * 26 + c, (f.get(r * 26 + c) || 0) + 1);
}
this.formula[row][column.charCodeAt(0) - 65] = f;
return this.get(row, column);
}
}2Optimal (dependency graph with eager updates)
O(1) get, O(26² + P) for set and sumReads are lookups; a write touches the expanded ranges and every dependency path P that leads away from the changed cell.O(26² · F)The reference and dependent maps together store each formula's cells twice.Keep every cell's current value up to date so that get is a plain lookup. Each formula cell remembers its referenced cells with counts, and each cell also remembers its dependents: which formula cells mention it and how many times. When a cell's value changes by d, every dependent changes by d times its count, and that change is pushed further along the same way. Because there are no cycles, the pushing stops.
- Cells get an id
row * 26 + col. Keepval[id],refs[id](cell -> count) anddeps[id](dependent -> count). clear(id): for each(ref, cnt)inrefs[id], removeidfromdeps[ref]; then emptyrefs[id].set:clear(id), thenpropagate(id, v - val[id]).sum:clear(id), expandnumbersinto counts, record them inrefs[id]anddeps[ref], compute the new value from the current values, andpropagate(id, newValue - val[id]).propagate(id, d): if d is 0 stop; add d toval[id], then callpropagate(dep, d * cnt)for each(dep, cnt)indeps[id].getreturnsval[id].
class Excel {
private final int[] val = new int[27 * 26];
private final List<Map<Integer, Integer>> refs = new ArrayList<>(), deps = new ArrayList<>();
public Excel(int height, char width) {
for (int i = 0; i < 27 * 26; i++) {
refs.add(new HashMap<>());
deps.add(new HashMap<>());
}
}
private void clear(int id) {
for (int ref : refs.get(id).keySet()) deps.get(ref).remove(id);
refs.get(id).clear();
}
private void propagate(int id, int delta) {
if (delta == 0) return;
val[id] += delta;
for (Map.Entry<Integer, Integer> e : deps.get(id).entrySet()) propagate(e.getKey(), delta * e.getValue());
}
public void set(int row, char column, int v) {
int id = row * 26 + (column - 'A');
clear(id);
propagate(id, v - val[id]);
}
public int get(int row, char column) {
return val[row * 26 + (column - 'A')];
}
public int sum(int row, char column, String[] numbers) {
int id = row * 26 + (column - 'A');
clear(id);
Map<Integer, Integer> f = refs.get(id);
for (String s : numbers) {
String[] parts = s.split(":");
String last = parts[parts.length - 1];
int r1 = Integer.parseInt(parts[0].substring(1)), c1 = parts[0].charAt(0) - 'A';
int r2 = Integer.parseInt(last.substring(1)), c2 = last.charAt(0) - 'A';
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++) f.merge(r * 26 + c, 1, Integer::sum);
}
int total = 0;
for (Map.Entry<Integer, Integer> e : f.entrySet()) {
deps.get(e.getKey()).put(id, e.getValue());
total += val[e.getKey()] * e.getValue();
}
propagate(id, total - val[id]);
return val[id];
}
}class Excel:
def __init__(self, height: int, width: str):
self.val = [0] * (27 * 26)
self.refs = [{} for _ in range(27 * 26)]
self.deps = [{} for _ in range(27 * 26)]
def _clear(self, cid: int) -> None:
for ref in self.refs[cid]:
self.deps[ref].pop(cid, None)
self.refs[cid] = {}
def _propagate(self, cid: int, delta: int) -> None:
if delta == 0:
return
self.val[cid] += delta
for dep, cnt in self.deps[cid].items():
self._propagate(dep, delta * cnt)
def set(self, row: int, column: str, val: int) -> None:
cid = row * 26 + ord(column) - ord("A")
self._clear(cid)
self._propagate(cid, val - self.val[cid])
def get(self, row: int, column: str) -> int:
return self.val[row * 26 + ord(column) - ord("A")]
def sum(self, row: int, column: str, numbers: List[str]) -> int:
cid = row * 26 + ord(column) - ord("A")
self._clear(cid)
f = {}
for s in numbers:
parts = s.split(":")
first, last = parts[0], parts[-1]
r1, c1 = int(first[1:]), ord(first[0]) - ord("A")
r2, c2 = int(last[1:]), ord(last[0]) - ord("A")
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
f[r * 26 + c] = f.get(r * 26 + c, 0) + 1
self.refs[cid] = f
total = 0
for ref, cnt in f.items():
self.deps[ref][cid] = cnt
total += self.val[ref] * cnt
self._propagate(cid, total - self.val[cid])
return self.val[cid]class Excel {
vector<int> val;
vector<unordered_map<int, int>> refs, deps;
void clearCell(int id) {
for (auto& [ref, cnt] : refs[id]) deps[ref].erase(id);
refs[id].clear();
}
void propagate(int id, int delta) {
if (delta == 0) return;
val[id] += delta;
for (auto& [dep, cnt] : deps[id]) propagate(dep, delta * cnt);
}
public:
Excel(int height, char width) : val(27 * 26, 0), refs(27 * 26), deps(27 * 26) {}
void set(int row, char column, int v) {
int id = row * 26 + (column - 'A');
clearCell(id);
propagate(id, v - val[id]);
}
int get(int row, char column) {
return val[row * 26 + (column - 'A')];
}
int sum(int row, char column, vector<string> numbers) {
int id = row * 26 + (column - 'A');
clearCell(id);
unordered_map<int, int>& f = refs[id];
for (auto& s : numbers) {
size_t colon = s.find(':');
string first = s.substr(0, colon);
string last = colon == string::npos ? first : s.substr(colon + 1);
int r1 = stoi(first.substr(1)), c1 = first[0] - 'A';
int r2 = stoi(last.substr(1)), c2 = last[0] - 'A';
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++) f[r * 26 + c]++;
}
int total = 0;
for (auto& [ref, cnt] : f) {
deps[ref][id] = cnt;
total += val[ref] * cnt;
}
propagate(id, total - val[id]);
return val[id];
}
};class Excel {
constructor(height, width) {
this.val = new Array(27 * 26).fill(0);
this.refs = Array.from({ length: 27 * 26 }, () => new Map());
this.deps = Array.from({ length: 27 * 26 }, () => new Map());
}
clear(id) {
for (const ref of this.refs[id].keys()) this.deps[ref].delete(id);
this.refs[id] = new Map();
}
propagate(id, delta) {
if (delta === 0) return;
this.val[id] += delta;
for (const [dep, cnt] of this.deps[id]) this.propagate(dep, delta * cnt);
}
set(row, column, val) {
const id = row * 26 + (column.charCodeAt(0) - 65);
this.clear(id);
this.propagate(id, val - this.val[id]);
}
get(row, column) {
return this.val[row * 26 + (column.charCodeAt(0) - 65)];
}
sum(row, column, numbers) {
const id = row * 26 + (column.charCodeAt(0) - 65);
this.clear(id);
const f = this.refs[id];
for (const s of numbers) {
const parts = s.split(":");
const first = parts[0], last = parts[parts.length - 1];
const r1 = Number(first.slice(1)), c1 = first.charCodeAt(0) - 65;
const r2 = Number(last.slice(1)), c2 = last.charCodeAt(0) - 65;
for (let r = r1; r <= r2; r++)
for (let c = c1; c <= c2; c++) f.set(r * 26 + c, (f.get(r * 26 + c) || 0) + 1);
}
let total = 0;
for (const [ref, cnt] of f) {
this.deps[ref].set(id, cnt);
total += this.val[ref] * cnt;
}
this.propagate(id, total - this.val[id]);
return this.val[id];
}
}Edge cases to test
- A cell listed several times in one formula, or inside overlapping ranges, counts once per mention
seton a formula cell removes the formula- Chains of formulas: a change must reach cells that depend on it indirectly
- A formula that references empty cells (value 0)
Hints
Hint 1
A formula is just a multiset of cells: expand every range into its cells and count how often each cell appears.
Hint 2
The simplest design stores the formula and evaluates it recursively each time someone reads the cell.
Hint 3
To make reads O(1), also store, for each cell, which formula cells depend on it and with what multiplicity. When a value changes by d, every dependent changes by d times that multiplicity, and so on down the chain.
FAQ
What is the best time complexity for Design Excel Sum Formula?
Optimal (dependency graph with eager updates) runs in O(1) get, O(26² + P) for set and sum time and O(26² · F) extra space. Reads are lookups; a write touches the expanded ranges and every dependency path P that leads away from the changed cell.
Which pattern does Design Excel Sum Formula use?
It is a design data structures problem that uses the dependency graph pattern.
Is there a brute force solution for Design Excel Sum Formula?
Yes. Brute force (evaluate formulas on every read) takes O(1) set, O(26² · F) sum, get up to O(P · 26²) time and O(26² · F) space. Store for each cell either a plain value or a formula, kept as a map from referenced cell to how many times it is mentioned.
Which edge cases should I test for Design Excel Sum Formula?
A cell listed several times in one formula, or inside overlapping ranges, counts once per mention; set on a formula cell removes the formula; Chains of formulas: a change must reach cells that depend on it indirectly; A formula that references empty cells (value 0).