Watch 10 video solutions for Design Spreadsheet, a medium level problem involving Array, Hash Table, String. This walkthrough by codestorywithMIK has 5,313 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
Constraints:
1 <= rows <= 1030 <= value <= 105"=X+Y", where X and Y are either valid cell references or non-negative integers with values less than or equal to 105.'A' to 'Z' followed by a row number between 1 and rows.104 calls will be made in total to setCell, resetCell, and getValue.Problem Overview: Design a spreadsheet system that stores values in cells and evaluates simple expressions referencing other cells. Each cell can hold a number or participate in a formula such as =A1+B2. The system must support updating cells, resetting them, and computing the result of expressions using current values.
Approach 1: 2D Matrix Simulation (O(1) access, O(L) evaluation)
The most direct implementation uses a fixed matrix to represent the spreadsheet grid. Each cell stores its numeric value, and operations like set or reset simply update the matrix position derived from the cell label (for example converting A1 into row/column indices). When evaluating an expression, parse the string and fetch values from the matrix for each referenced cell. Access to any cell is O(1), while evaluating a formula takes O(L) time where L is the expression length. Space complexity is O(R Ă— C) for the grid. This approach works well when the spreadsheet size is fixed and relatively small.
Approach 2: Hash Table Cell Storage (O(1) average operations)
A more flexible design stores only active cells in a hash table mapping the cell label (like "A1") to its value. Updates and resets become simple hash operations. When computing an expression, parse the string, extract referenced cells, and perform hash lookups for their values. Missing cells default to zero. Hash lookups run in O(1) average time, and expression parsing costs O(L). Space complexity becomes O(K), where K is the number of cells that have been written. This avoids allocating a full grid and is typically the preferred design for interview settings.
Expression parsing is straightforward: iterate through the string, split operands around the '+' operator, and check whether each token is a number or a cell reference. Cell references require converting column letters and row digits before performing the lookup. String processing dominates runtime, which is why the complexity is proportional to the expression length.
Recommended for interviews: The hash table approach is usually expected. It demonstrates good use of hash tables for constant‑time lookups and clean handling of sparse spreadsheets. A matrix simulation shows basic understanding of arrays and matrix indexing, but the hash table design scales better and keeps memory usage proportional to the number of populated cells.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| 2D Matrix Simulation | O(1) cell access, O(L) formula evaluation | O(R Ă— C) | When spreadsheet size is fixed and small |
| Hash Table Cell Storage | O(1) average updates/lookups, O(L) evaluation | O(K) | General case with sparse cells and dynamic updates |