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 theheight
and thewidth
of the sheet. The sheet is an integer matrixmat
of sizeheight 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 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 bynumbers
and 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 <= 7
and'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")
.
Examples
Example 1:
|
|
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 toset
,get
, andsum
.
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
- Represent the Excel sheet as a 2D array. For each cell, store its value and a map of dependencies (which cells it sums over).
- When
set
is called, clear dependencies for that cell, set its value, and update all cells that depend on it. - 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. - For
get
, return the current value of the cell. - Use DFS to update all cells that depend on a changed cell.
- Parse cell references and ranges to row/column indices.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(k)
per operation, wherek
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)
, wheren*m
is the size of the matrix andd
is the number of dependencies tracked for sum formulas.