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.
"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.
"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.
mat[1]['A'] == sum(1, "B") and mat[1]['B'] == sum(1, "A").
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 <= 1001 <= numbers.length <= 5numbers[i] has the format "ColRow" or "ColRow1:ColRow2".100 calls will be made to set, get, and sum.Problem Overview: You need to implement a simplified Excel spreadsheet that supports set, get, and sum operations. The tricky part is that a SUM formula can reference individual cells or ranges (like A1:B3), and when any referenced cell changes, dependent cells must update automatically.
Approach 1: Direct Recalculation (Brute Force) (Time: O(r * c) per sum, Space: O(1))
The simplest implementation stores raw values in a 2D grid (matrix). When a sum formula is defined, you immediately compute the total by iterating through every referenced cell or expanding each range into individual coordinates. The result is written directly into the target cell. This works but ignores dependencies: if a referenced cell later changes, the computed sum becomes stale unless recomputed manually. The approach mainly helps understand the mechanics of range parsing and iteration across a matrix, but it does not model spreadsheet behavior correctly.
Approach 2: Dependency Graph with Topological Propagation (Time: O(k) update, Space: O(n^2))
A correct spreadsheet model tracks relationships between cells. Each cell can depend on multiple source cells if it contains a SUM formula. Represent these relationships as a directed graph where edges point from a source cell to the cells that depend on it. When a cell changes through set, you propagate updates through its dependents using DFS or topological traversal. Each dependent recomputes its value by aggregating contributions from the cells it references.
The key idea is storing a frequency map of dependencies for each formula cell. For example, if a formula references a range, each cell inside the range contributes a count in the dependency map. When a source value changes, you push the delta through the dependency graph and update downstream cells. This turns recalculation into a graph propagation problem and avoids recomputing unrelated cells.
This design closely mirrors spreadsheet engines and naturally fits problems involving graph relationships and topological sort. The grid itself can still be stored as a 2D array, while formulas maintain adjacency lists for dependency tracking.
Recommended for interviews: Interviewers expect the dependency graph approach. A brute force recalculation shows you understand the grid and range parsing, but the graph-based design demonstrates system thinking. Maintaining dependencies and propagating updates efficiently is the core challenge, and solving it with a graph plus incremental updates shows strong design and algorithm skills.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Recalculation | O(r * c) per SUM | O(1) | Good for understanding range parsing or when formulas never change after computation |
| Dependency Graph Propagation | O(k) per update | O(n^2) | Best for spreadsheet-style systems where cell updates must propagate efficiently |
| Topological Update via DFS/BFS | O(V + E) | O(V + E) | Useful when modeling full dependency graphs with many chained formulas |
【Edward Shi】LeetCode 631. Design Excel Sum Formula 设计 Excel 求和公式 |算法面试|刷题找工作|北美CS求职|力扣 • Edward Shi • 703 views views
Watch 2 more video solutions →Practice Design Excel Sum Formula with our built-in code editor and test cases.
Practice on FleetCode