# Design Spreadsheet **Difficulty:** MEDIUM [External](https://leetcode.com/problems/design-spreadsheet) Canonical: https://scaleengineer.com/dsa/problems/design-spreadsheet **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Data structures:** Array, Hash Table, String, Matrix **Companies:** [Rippling](https://scaleengineer.com/companies/rippling) --- ## Problem A spreadsheet is a grid with 26 columns (labeled from `'A'` to `'Z'`) and a given number of `rows`. Each cell in the spreadsheet can hold an integer value between 0 and 105. Implement the `Spreadsheet` class: * `Spreadsheet(int rows)` Initializes a spreadsheet with 26 columns (labeled `'A'` to `'Z'`) and the specified number of rows. All cells are initially set to 0. * `void setCell(String cell, int value)` Sets the value of the specified `cell`. The cell reference is provided in the format `"AX"` (e.g., `"A1"`, `"B10"`), where the letter represents the column (from `'A'` to `'Z'`) and the number represents a **1-indexed** row. * `void resetCell(String cell)` Resets the specified cell to 0. * `int getValue(String formula)` Evaluates a formula of the form `"=X+Y"`, where `X` and `Y` are **either** cell references or non-negative integers, and returns the computed sum. **Note:** If `getValue` references a cell that has not been explicitly set using `setCell`, its value is considered 0. **Example 1:** **Input:** \["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"\] \[\[3\], \["=5+7"\], \["A1", 10\], \["=A1+6"\], \["B2", 15\], \["=A1+B2"\], \["A1"\], \["=A1+B2"\]\] **Output:** \[null, 12, null, 16, null, 25, null, 15\] **Explanation** Spreadsheet spreadsheet = new Spreadsheet(3); // Initializes a spreadsheet with 3 rows and 26 columns spreadsheet.getValue("=5+7"); // returns 12 (5+7) spreadsheet.setCell("A1", 10); // sets A1 to 10 spreadsheet.getValue("=A1+6"); // returns 16 (10+6) spreadsheet.setCell("B2", 15); // sets B2 to 15 spreadsheet.getValue("=A1+B2"); // returns 25 (10+15) spreadsheet.resetCell("A1"); // resets A1 to 0 spreadsheet.getValue("=A1+B2"); // returns 15 (0+15) **Constraints:** * `1 <= rows <= 103` * `0 <= value <= 105` * The formula is always in the format `"=X+Y"`, where `X` and `Y` are either valid cell references or **non-negative** integers with values less than or equal to `105`. * Each cell reference consists of a capital letter from `'A'` to `'Z'` followed by a row number between `1` and `rows`. * At most `104` calls will be made in **total** to `setCell`, `resetCell`, and `getValue`. # Approaches ## Using a HashMap for Sparse Cell Storage This approach uses a `HashMap` to store the values of the cells. The key of the map is the cell reference string (e.g., "A1"), and the value is the integer stored in that cell. This method is advantageous when the spreadsheet is very large and sparse (most cells are 0), as it only stores the cells that have been explicitly set. **Time:** `Spreadsheet(rows)`: O(1). `setCell`/`resetCell`: Average O(L) where L is the length of the cell string key. `getValue`: O(F) where F is the length of the formula string. · **Space:** O(C * L), where C is the number of non-zero cells and L is the average length of a cell string key. This is because the map stores the string keys. **Pros:** Fast O(1) initialization.; Space efficient if the number of set cells is very small compared to the total grid size (`rows` * 26). **Cons:** Higher memory overhead per cell compared to a simple integer array due to HashMap's internal structure and storing string keys.; Slightly slower access times due to hash computation and potential collisions compared to direct array indexing.; For the given constraints, it is likely to use more memory than a 2D array. ### Explanation This approach models the spreadsheet as a sparse grid, storing only the cells that have been assigned a value. A `java.util.HashMap` is the core data structure. * **Data Storage**: A `HashMap cells` maps a cell's string identifier (e.g., `"A1"`) to its integer value. * **Initialization**: The `Spreadsheet` constructor is very fast, as it only needs to create a new empty `HashMap`. * **`setCell`**: To set a cell's value, we simply add or update an entry in the map: `cells.put(cell, value)`. * **`resetCell`**: To reset a cell, we remove its entry from the map: `cells.remove(cell)`. This is efficient as subsequent lookups for this cell will default to 0. * **`getValue`**: This method involves parsing the formula string. A helper function, `parseTerm`, determines if a term is a number or a cell reference. For cell references, it queries the map using `cells.getOrDefault(term, 0)`, which conveniently returns 0 if the cell hasn't been set. Here is a sample implementation in Java: ```java import java.util.HashMap; import java.util.Map; class Spreadsheet { private Map cells; private int rows; private final int cols = 26; public Spreadsheet(int rows) { this.rows = rows; this.cells = new HashMap<>(); } public void setCell(String cell, int value) { cells.put(cell, value); } public void resetCell(String cell) { cells.remove(cell); } private int parseTerm(String term) { if (Character.isLetter(term.charAt(0))) { return cells.getOrDefault(term, 0); } else { return Integer.parseInt(term); } } public int getValue(String formula) { String[] parts = formula.substring(1).split("\\+"); String term1Str = parts[0]; String term2Str = parts[1]; int val1 = parseTerm(term1Str); int val2 = parseTerm(term2Str); return val1 + val2; } } ``` ### Algorithm * Initialize a `HashMap cells` to store cell values. * In `setCell(cell, value)`, call `cells.put(cell, value)`. * In `resetCell(cell)`, call `cells.remove(cell)` to revert the cell's value to the default of 0. * In `getValue(formula)`: * Parse the formula `"=X+Y"` to extract terms `X` and `Y`. * Create a helper function `evaluate(term)`: * If `term` starts with a letter, it's a cell reference. Return `cells.getOrDefault(term, 0)`. * Otherwise, it's a number. Return `Integer.parseInt(term)`. * Return the sum of the evaluated terms `X` and `Y`. ## Using a 2D Array for Direct Cell Access This approach uses a 2D integer array to represent the spreadsheet grid directly. A cell reference like "A1" is parsed into `(row, column)` indices to access the array. This provides the fastest possible access to cell values and is generally the most efficient method for the given constraints. **Time:** `Spreadsheet(rows)`: O(R * C) = O(R) for array initialization. `setCell`/`resetCell`/`getValue`: O(L) for parsing the string arguments (cell or formula), which is effectively constant time. · **Space:** O(R * C), where R is the number of rows and C is the number of columns (26). Since C is constant, this is O(R). **Pros:** Extremely fast, true O(1) access to cell values after parsing.; Lower memory overhead per cell compared to a HashMap.; Predictable and often better space usage for the given problem constraints. **Cons:** Initialization takes O(rows) time and space, which can be considered wasteful if `rows` is very large and the grid remains very sparse. ### Explanation This approach uses a 2D array, `int[][] grid`, which directly mirrors the structure of the spreadsheet. This allows for constant-time access to any cell once its reference is parsed into row and column indices. * **Data Storage**: An `int[][] grid` of size `rows x 26` is used. `grid[r][c]` stores the value of the cell at row `r+1` and column `c`. * **Initialization**: The `Spreadsheet` constructor allocates the `rows x 26` array. Java automatically initializes all elements to 0. * **Cell Parsing**: A crucial helper function, `parseCellToCoords(String cell)`, is needed to translate string references like `"B10"` into array indices `[9, 1]`. This is done by converting the character `'B'` to a column index (`'B' - 'A' = 1`) and the string `"10"` to a 0-indexed row (`10 - 1 = 9`). * **`setCell` / `resetCell`**: These methods first call `parseCellToCoords` to get the `(row, col)` indices and then directly access `grid[row][col]` to set the value or reset it to 0. * **`getValue`**: Similar to the HashMap approach, this method parses the formula. When a term is identified as a cell reference, `parseCellToCoords` is used to find its indices, and the value is retrieved directly from the `grid`. Here is a sample implementation in Java: ```java class Spreadsheet { private int[][] grid; private int rows; private final int cols = 26; public Spreadsheet(int rows) { this.rows = rows; this.grid = new int[rows][this.cols]; } private int[] parseCellToCoords(String cell) { int col = cell.charAt(0) - 'A'; int row = Integer.parseInt(cell.substring(1)) - 1; return new int[]{row, col}; } public void setCell(String cell, int value) { int[] coords = parseCellToCoords(cell); grid[coords[0]][coords[1]] = value; } public void resetCell(String cell) { int[] coords = parseCellToCoords(cell); grid[coords[0]][coords[1]] = 0; } private int parseTerm(String term) { if (Character.isLetter(term.charAt(0))) { int[] coords = parseCellToCoords(term); return grid[coords[0]][coords[1]]; } else { return Integer.parseInt(term); } } public int getValue(String formula) { String[] parts = formula.substring(1).split("\\+"); String term1Str = parts[0]; String term2Str = parts[1]; int val1 = parseTerm(term1Str); int val2 = parseTerm(term2Str); return val1 + val2; } } ``` ### Algorithm * Initialize an `int[][] grid` of size `rows x 26`. * Create a helper function `parseCellToCoords(cell)`: * `col = cell.charAt(0) - 'A'`. * `row = Integer.parseInt(cell.substring(1)) - 1`. * Return `[row, col]`. * In `setCell(cell, value)`: * Get `[row, col]` from `parseCellToCoords(cell)`. * Set `grid[row][col] = value`. * In `resetCell(cell)`: * Get `[row, col]` from `parseCellToCoords(cell)`. * Set `grid[row][col] = 0`. * In `getValue(formula)`: * Parse the formula to get terms `X` and `Y`. * Create a helper `evaluate(term)`: * If `term` is a cell reference, get `[row, col]` from `parseCellToCoords(term)` and return `grid[row][col]`. * Otherwise, parse it as an integer. * Return the sum of the evaluated terms. # Solutions ### Java ```java class Spreadsheet { private Map < String , Integer > d = new HashMap <>(); public Spreadsheet ( int rows ) { } public void setCell ( String cell , int value ) { d . put ( cell , value ); } public void resetCell ( String cell ) { d . remove ( cell ); } public int getValue ( String formula ) { int ans = 0 ; for ( String cell : formula . substring ( 1 ). split ( "\\+" )) { ans += Character . isDigit ( cell . charAt ( 0 )) ? Integer . parseInt ( cell ) : d . getOrDefault ( cell , 0 ); } return ans ; } } /** * Your Spreadsheet object will be instantiated and called as such: * Spreadsheet obj = new Spreadsheet(rows); * obj.setCell(cell,value); * obj.resetCell(cell); * int param_3 = obj.getValue(formula); */ ``` ### CPP ```cpp class Spreadsheet { private: unordered_map < string , int > d ; public: Spreadsheet ( int rows ) {} void setCell ( string cell , int value ) { d [ cell ] = value ; } void resetCell ( string cell ) { d . erase ( cell ); } int getValue ( string formula ) { int ans = 0 ; stringstream ss ( formula . substr ( 1 )); string cell ; while ( getline ( ss , cell , '+' )) { if ( isdigit ( cell [ 0 ])) { ans += stoi ( cell ); } else { ans += d . count ( cell ) ? d [ cell ] : 0 ; } } return ans ; } }; /** * Your Spreadsheet object will be instantiated and called as such: * Spreadsheet* obj = new Spreadsheet(rows); * obj->setCell(cell,value); * obj->resetCell(cell); * int param_3 = obj->getValue(formula); */ ``` ### Python ```python class Spreadsheet : def __init__ ( self , rows : int ): self . d = {} def setCell ( self , cell : str , value : int ) -> None : self . d [ cell ] = value def resetCell ( self , cell : str ) -> None : self . d . pop ( cell , None ) def getValue ( self , formula : str ) -> int : ans = 0 for cell in formula [ 1 :]. split ( "+" ): ans += int ( cell ) if cell [ 0 ]. isdigit () else self . d . get ( cell , 0 ) return ans # Your Spreadsheet object will be instantiated and called as such: # obj = Spreadsheet(rows) # obj.setCell(cell,value) # obj.resetCell(cell) # param_3 = obj.getValue(formula) ```