Design Excel Sum Formula - Video Solutions
Leetcode 631. Design Excel Sum Formula (bfs)
Design Excel Sum Formula - Video Solution
Watch 3 video solutions for Design Excel Sum Formula, a hard level problem involving Array, Graph, Design. This walkthrough by LetsCode has 2,467 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 theheightand thewidthof the sheet. The sheet is an integer matrixmatof sizeheight x widthwith 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 atmat[row][column]to beval.int get(int row, char column)Returns the value atmat[row][column].int sum(int row, char column, List<String> numbers)Sets the value atmat[row][column]to be the sum of cells represented bynumbersand returns the value atmat[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 cellmat[7]['F'].
- For example,
"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 cellsmat[i][j]for3 <= i <= 7and'B' <= j <= 'F'.
- For example,
Note: You could assume that there will not be any circular sum reference.
- For example,
mat[1]['A'] == sum(1, "B")andmat[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".- At most
100calls will be made toset,get, andsum.
Approach Overview
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.
Complexity Analysis
| 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 |