Design Excel Sum Formula

Problem

Design the basic function of Excel and implement the function of the sum formula.

Implement the Excel class:

• Excel(int height, char width) Initializes the object with the height and the width of the sheet. The sheet is an integer matrix mat of size height x width with the row index in the range [1, height] and the column index in the range ['A', width]. All the values should be zero initially.
• void set(int row, char column, int val) Changes the value at mat[row][column] to be val.
• int get(int row, char column) Returns the value at mat[row][column].
• int sum(int row, char column, List<String> numbers) Sets the value at mat[row][column] to be the sum of cells represented by numbers and returns the value at mat[row][column]. This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers[i] could be on the format:
  • "ColRow" that represents a single cell.
    • For example, "F7" represents the cell mat[7]['F'].
  • "ColRow1:ColRow2" that represents a range of cells. The range will always be a rectangle where "ColRow1" represent the position of the top-left cell, and "ColRow2" represents the position of the bottom-right cell.
    • For example, "B3:F7" represents the cells mat[i][j] for 3 <= i <= 7 and 'B' <= j <= 'F'.

Note: You could assume that there will not be any circular sum reference.

• For example, mat[1]['A'] == sum(1, "B") and mat[1]['B'] == sum(1, "A").

Examples

Example 1:

**Input**
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
**Output**
[null, null, 4, null, 6]
**Explanation**
Excel excel = new Excel(3, "C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
excel.set(1, "A", 2);
// set mat[1]["A"] to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
excel.sum(3, "C", ["A1", "A1:B2"]); // return 4
// set mat[3]["C"] to be the sum of value at mat[1]["A"] and the values sum of the rectangle range whose top-left cell is mat[1]["A"] and bottom-right cell is mat[2]["B"].
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
excel.set(2, "B", 2);
// set mat[2]["B"] to be 2. Note mat[3]["C"] should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
excel.get(3, "C"); // return 6

Constraints:

• 1 <= height <= 26
• 'A' <= width <= 'Z'
• 1 <= row <= height
• 'A' <= column <= width
• -100 <= val <= 100
• 1 <= numbers.length <= 5
• numbers[i] has the format "ColRow" or "ColRow1:ColRow2".
• At most 100 calls will be made to set, get, and sum.

Solution

Method 1 – Dependency Graph with DFS

Intuition

To support sum formulas and cell updates, we need to track dependencies between cells. When a cell is set or summed, we must update all dependent cells. We use a dependency graph and DFS to propagate changes efficiently.

Approach

1. Represent the Excel sheet as a 2D array. For each cell, store its value and a map of dependencies (which cells it sums over).
2. When set is called, clear dependencies for that cell, set its value, and update all cells that depend on it.
3. When sum is called, parse the ranges, build the dependency map for the cell, and compute its value by summing the referenced cells. Update all dependents.
4. For get, return the current value of the cell.
5. Use DFS to update all cells that depend on a changed cell.
6. Parse cell references and ranges to row/column indices.

Code

C++

class Excel {
    int h, w;
    vector<vector<int>> mat;
    vector<vector<unordered_map<int, int>>> deps;
    unordered_map<int, vector<pair<int, int>>> rev;
    int idx(char c) { return c - 'A'; }
    int key(int r, int c) { return r * 26 + c; }
    void update(int r, int c) {
        int sum = 0;
        for (auto& [k, cnt] : deps[r][c]) {
            int rr = k / 26, cc = k % 26;
            sum += mat[rr][cc] * cnt;
        }
        mat[r][c] = sum;
        for (auto& [rr, cc] : rev[key(r, c)]) update(rr, cc);
    }
public:
    Excel(int height, char width) : h(height), w(idx(width) + 1), mat(h, vector<int>(w)), deps(h, vector<unordered_map<int, int>>(w)) {}
    void set(int r, char c, int v) {
        r--;
        deps[r][idx(c)].clear();
        mat[r][idx(c)] = v;
        for (auto& [rr, cc] : rev[key(r, idx(c))]) update(rr, cc);
    }
    int get(int r, char c) {
        return mat[r-1][idx(c)];
    }
    int sum(int r, char c, vector<string> numbers) {
        r--;
        deps[r][idx(c)].clear();
        for (string& s : numbers) {
            int r1, c1, r2, c2;
            if (s.find(":") == string::npos) {
                c1 = idx(s[0]); r1 = stoi(s.substr(1)) - 1;
                c2 = c1; r2 = r1;
            } else {
                c1 = idx(s[0]); r1 = stoi(s.substr(1, s.find(":")-1)) - 1;
                c2 = idx(s[s.find(":")+1]); r2 = stoi(s.substr(s.find(":")+2)) - 1;
            }
            for (int i = r1; i <= r2; ++i) for (int j = c1; j <= c2; ++j) deps[r][idx(c)][key(i, j)]++;
        }
        update(r, idx(c));
        return mat[r][idx(c)];
    }
};

Go

type Excel struct {
    h, w int
    mat [][]int
    deps [][][]map[[2]int]int
}

func idx(c byte) int { return int(c - 'A') }

func NewExcel(height int, width byte) *Excel {
    h, w := height, idx(width)+1
    mat := make([][]int, h)
    deps := make([][][]map[[2]int]int, h)
    for i := 0; i < h; i++ {
        mat[i] = make([]int, w)
        deps[i] = make([][]map[[2]int]int, w)
        for j := 0; j < w; j++ {
            deps[i][j] = make(map[[2]int]int)
        }
    }
    return &Excel{h, w, mat, deps}
}

func (e *Excel) Set(r int, c byte, v int) {
    r--
    e.deps[r][idx(c)] = make(map[[2]int]int)
    e.mat[r][idx(c)] = v
}

func (e *Excel) Get(r int, c byte) int {
    return e.mat[r-1][idx(c)]
}

func (e *Excel) Sum(r int, c byte, numbers []string) int {
    r--
    e.deps[r][idx(c)] = make(map[[2]int]int)
    for _, s := range numbers {
        if i := strings.Index(s, ":"); i == -1 {
            col := idx(s[0])
            row, _ := strconv.Atoi(s[1:])
            e.deps[r][idx(c)][[2]int{row-1, col}]++
        } else {
            col1 := idx(s[0])
            row1, _ := strconv.Atoi(s[1:i])
            col2 := idx(s[i+1])
            row2, _ := strconv.Atoi(s[i+2:])
            for rr := row1 - 1; rr <= row2 - 1; rr++ {
                for cc := col1; cc <= col2; cc++ {
                    e.deps[r][idx(c)][[2]int{rr, cc}]++
                }
            }
        }
    }
    sum := 0
    for k, cnt := range e.deps[r][idx(c)] {
        sum += e.mat[k[0]][k[1]] * cnt
    }
    e.mat[r][idx(c)] = sum
    return sum
}

Java

public class Excel {
    private int h, w;
    private int[][] mat;
    private Map<String, Map<String, Integer>> deps;
    private int idx(char c) { return c - 'A'; }
    public Excel(int height, char width) {
        h = height;
        w = idx(width) + 1;
        mat = new int[h][w];
        deps = new HashMap<>();
    }
    public void set(int r, char c, int v) {
        mat[r-1][idx(c)] = v;
        deps.remove((r-1) + "," + idx(c));
    }
    public int get(int r, char c) {
        return mat[r-1][idx(c)];
    }
    public int sum(int r, char c, List<String> numbers) {
        Map<String, Integer> dep = new HashMap<>();
        for (String s : numbers) {
            if (!s.contains(":")) {
                int col = idx(s.charAt(0));
                int row = Integer.parseInt(s.substring(1)) - 1;
                dep.put(row + "," + col, dep.getOrDefault(row + "," + col, 0) + 1);
            } else {
                int i = s.indexOf(":");
                int col1 = idx(s.charAt(0));
                int row1 = Integer.parseInt(s.substring(1, i)) - 1;
                int col2 = idx(s.charAt(i+1));
                int row2 = Integer.parseInt(s.substring(i+2)) - 1;
                for (int rr = row1; rr <= row2; rr++)
                    for (int cc = col1; cc <= col2; cc++)
                        dep.put(rr + "," + cc, dep.getOrDefault(rr + "," + cc, 0) + 1);
            }
        }
        int sum = 0;
        for (Map.Entry<String, Integer> e : dep.entrySet()) {
            String[] parts = e.getKey().split(",");
            int rr = Integer.parseInt(parts[0]), cc = Integer.parseInt(parts[1]);
            sum += mat[rr][cc] * e.getValue();
        }
        mat[r-1][idx(c)] = sum;
        deps.put((r-1) + "," + idx(c), dep);
        return sum;
    }
}

Kotlin

class Excel(height: Int, width: Char) {
    private val h = height
    private val w = width - 'A' + 1
    private val mat = Array(h) { IntArray(w) }
    private val deps = mutableMapOf<Pair<Int, Int>, MutableMap<Pair<Int, Int>, Int>>() 
    private fun idx(c: Char) = c - 'A'
    fun set(r: Int, c: Char, v: Int) {
        mat[r-1][idx(c)] = v
        deps.remove(Pair(r-1, idx(c)))
    }
    fun get(r: Int, c: Char): Int = mat[r-1][idx(c)]
    fun sum(r: Int, c: Char, numbers: List<String>): Int {
        val dep = mutableMapOf<Pair<Int, Int>, Int>()
        for (s in numbers) {
            if (":" !in s) {
                val col = idx(s[0])
                val row = s.substring(1).toInt() - 1
                dep[Pair(row, col)] = dep.getOrDefault(Pair(row, col), 0) + 1
            } else {
                val i = s.indexOf(":")
                val col1 = idx(s[0])
                val row1 = s.substring(1, i).toInt() - 1
                val col2 = idx(s[i+1])
                val row2 = s.substring(i+2).toInt() - 1
                for (rr in row1..row2) for (cc in col1..col2) dep[Pair(rr, cc)] = dep.getOrDefault(Pair(rr, cc), 0) + 1
            }
        }
        var sum = 0
        for ((k, v) in dep) sum += mat[k.first][k.second] * v
        mat[r-1][idx(c)] = sum
        deps[Pair(r-1, idx(c))] = dep
        return sum
    }
}

Python

class Excel:
    def __init__(self, height: int, width: str):
        self.h = height
        self.w = ord(width) - ord('A') + 1
        self.mat = [[0] * self.w for _ in range(self.h)]
        self.deps: dict[tuple[int, int], dict[tuple[int, int], int]] = {}
    def set(self, r: int, c: str, v: int) -> None:
        self.mat[r-1][ord(c)-ord('A')] = v
        self.deps.pop((r-1, ord(c)-ord('A')), None)
    def get(self, r: int, c: str) -> int:
        return self.mat[r-1][ord(c)-ord('A')]
    def sum(self, r: int, c: str, numbers: list[str]) -> int:
        dep: dict[tuple[int, int], int] = {}
        for s in numbers:
            if ':' not in s:
                col = ord(s[0]) - ord('A')
                row = int(s[1:]) - 1
                dep[(row, col)] = dep.get((row, col), 0) + 1
            else:
                i = s.index(':')
                col1 = ord(s[0]) - ord('A')
                row1 = int(s[1:i]) - 1
                col2 = ord(s[i+1]) - ord('A')
                row2 = int(s[i+2:]) - 1
                for rr in range(row1, row2+1):
                    for cc in range(col1, col2+1):
                        dep[(rr, cc)] = dep.get((rr, cc), 0) + 1
        s = 0
        for (rr, cc), cnt in dep.items():
            s += self.mat[rr][cc] * cnt
        self.mat[r-1][ord(c)-ord('A')] = s
        self.deps[(r-1, ord(c)-ord('A'))] = dep
        return s

Rust

struct Excel {
    h: usize,
    w: usize,
    mat: Vec<Vec<i32>>,
    deps: std::collections::HashMap<(usize, usize), std::collections::HashMap<(usize, usize), i32>>,
}

impl Excel {
    fn new(height: i32, width: char) -> Self {
        let h = height as usize;
        let w = (width as u8 - b'A' + 1) as usize;
        Self {
            h,
            w,
            mat: vec![vec![0; w]; h],
            deps: std::collections::HashMap::new(),
        }
    }
    fn set(&mut self, r: i32, c: char, v: i32) {
        self.mat[(r-1) as usize][(c as u8 - b'A') as usize] = v;
        self.deps.remove(&((r-1) as usize, (c as u8 - b'A') as usize));
    }
    fn get(&self, r: i32, c: char) -> i32 {
        self.mat[(r-1) as usize][(c as u8 - b'A') as usize]
    }
    fn sum(&mut self, r: i32, c: char, numbers: Vec<String>) -> i32 {
        let mut dep = std::collections::HashMap::new();
        for s in numbers.iter() {
            if !s.contains(":") {
                let col = (s.as_bytes()[0] - b'A') as usize;
                let row = s[1..].parse::<usize>().unwrap() - 1;
                *dep.entry((row, col)).or_insert(0) += 1;
            } else {
                let i = s.find(":").unwrap();
                let col1 = (s.as_bytes()[0] - b'A') as usize;
                let row1 = s[1..i].parse::<usize>().unwrap() - 1;
                let col2 = (s.as_bytes()[i+1] - b'A') as usize;
                let row2 = s[i+2..].parse::<usize>().unwrap() - 1;
                for rr in row1..=row2 {
                    for cc in col1..=col2 {
                        *dep.entry((rr, cc)).or_insert(0) += 1;
                    }
                }
            }
        }
        let mut s = 0;
        for ((rr, cc), cnt) in dep.iter() {
            s += self.mat[*rr][*cc] * cnt;
        }
        self.mat[(r-1) as usize][(c as u8 - b'A') as usize] = s;
        self.deps.insert(((r-1) as usize, (c as u8 - b'A') as usize), dep);
        s
    }
}

TypeScript

class Excel {
    private h: number;
    private w: number;
    private mat: number[][];
    private deps: Map<string, Map<string, number>>;
    constructor(height: number, width: string) {
        this.h = height;
        this.w = width.charCodeAt(0) - 'A'.charCodeAt(0) + 1;
        this.mat = Array.from({length: this.h}, () => Array(this.w).fill(0));
        this.deps = new Map();
    }
    set(r: number, c: string, v: number): void {
        this.mat[r-1][c.charCodeAt(0)-65] = v;
        this.deps.delete(`${r-1},${c.charCodeAt(0)-65}`);
    }
    get(r: number, c: string): number {
        return this.mat[r-1][c.charCodeAt(0)-65];
    }
    sum(r: number, c: string, numbers: string[]): number {
        const dep = new Map<string, number>();
        for (const s of numbers) {
            if (!s.includes(':')) {
                const col = s.charCodeAt(0) - 65;
                const row = parseInt(s.slice(1)) - 1;
                dep.set(`${row},${col}`, (dep.get(`${row},${col}`) || 0) + 1);
            } else {
                const i = s.indexOf(':');
                const col1 = s.charCodeAt(0) - 65;
                const row1 = parseInt(s.slice(1, i)) - 1;
                const col2 = s.charCodeAt(i+1) - 65;
                const row2 = parseInt(s.slice(i+2)) - 1;
                for (let rr = row1; rr <= row2; rr++)
                    for (let cc = col1; cc <= col2; cc++)
                        dep.set(`${rr},${cc}`, (dep.get(`${rr},${cc}`) || 0) + 1);
            }
        }
        let s = 0;
        for (const [k, cnt] of dep.entries()) {
            const [rr, cc] = k.split(',').map(Number);
            s += this.mat[rr][cc] * cnt;
        }
        this.mat[r-1][c.charCodeAt(0)-65] = s;
        this.deps.set(`${r-1},${c.charCodeAt(0)-65}`, dep);
        return s;
    }
}

Complexity

• ⏰ Time complexity: O(k) per operation, where k is the number of cells referenced in the sum formula. Each set/sum/get is efficient due to direct indexing and map lookups.
• 🧺 Space complexity: O(n*m + d), where n*m is the size of the matrix and d is the number of dependencies tracked for sum formulas.