Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Design, Matrix

Solution

LeetCode 3484 - Design Spreadsheet

Problem Understanding

This problem asks us to design a very small spreadsheet system that supports three operations on cells and one operation for evaluating simple formulas.

The spreadsheet always contains exactly 26 columns, labeled 'A' through 'Z', and a configurable number of rows. Each cell can store an integer value.

The class must support the following operations:

setCell(cell, value) stores a value into a cell.
resetCell(cell) resets a cell back to 0.
getValue(formula) evaluates a formula of the form "=X+Y".

The interesting part is formula evaluation. Each operand X and Y can be either:

A cell reference such as "A1" or "B10".
A non-negative integer such as "5" or "100".

For example:

"=5+7" evaluates to 12.
"=A1+6" evaluates to the value stored in A1 plus 6.
"=A1+B2" evaluates to the sum of the two referenced cells.

An important rule is that cells that have never been assigned a value behave as if they contain 0. Therefore, there is no need to explicitly initialize every cell.

The constraints are small:

At most 1000 rows.
At most 10,000 total operations.
Only very simple formulas are supported.
Formulas always have exactly one '+'.
Cell references are always valid.

These guarantees significantly simplify the implementation because we never need to handle invalid formulas, malformed cell references, dependency graphs, circular references, or complex expressions.

Important Edge Cases

A few cases are worth identifying immediately:

A formula may reference a cell that was never assigned. Its value must be treated as 0.
A cell may be reset after being assigned a value.
Both operands may be integers.
One operand may be an integer and the other a cell reference.
Row numbers can contain multiple digits, such as "A1000".

Because formulas are always valid and only involve addition of two operands, parsing is straightforward.

Approaches

Brute Force Approach

A direct implementation would create the entire spreadsheet as a two-dimensional array with rows × 26 cells.

During initialization, every cell would be explicitly filled with 0.

For setCell, we would convert the cell reference into row and column indices and update the corresponding position.

For resetCell, we would set that position back to 0.

For getValue, we would parse the formula and retrieve values either directly from the grid or from integer literals.

This approach is correct because every spreadsheet cell always has a stored value.

However, most cells may never be touched. Since unspecified cells are considered 0, allocating storage for all rows and columns is unnecessary.

Key Insight

The problem only cares about cells whose values differ from the default value of 0.

Instead of storing every cell, we can store only non-zero or explicitly assigned cells inside a hash map.

The cell reference string itself, such as "A1" or "B2", can serve as the key.

When:

A cell is assigned, store it in the hash map.
A cell is reset, remove it from the hash map.
A cell is queried, return the stored value if present, otherwise return 0.

Since formula evaluation only involves two operands, each lookup becomes a constant-time hash map operation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1) per operation	O(rows × 26)	Stores every cell explicitly
Optimal	O(1) per operation	O(k)	Stores only cells currently holding non-default values, where k is the number of stored cells

Algorithm Walkthrough

Create a hash map that maps cell references to their stored values.
During construction, initialize the hash map as empty. Since every unspecified cell is implicitly 0, no further setup is required.
For setCell(cell, value), store the value in the hash map using the cell reference as the key.
For resetCell(cell), remove the key from the hash map. After removal, future lookups automatically return 0.
For getValue(formula), remove the leading '=' character.
Split the remaining string at '+' to obtain the two operands.
Evaluate each operand independently:
If the first character is a digit, convert the operand into an integer.
Otherwise, treat it as a cell reference and look it up in the hash map.
If the cell is absent, use 0.
Add the two evaluated values and return the result.

Why it works

The hash map always contains exactly the cells whose current value differs from the implicit default state. Any cell not present in the map is interpreted as 0, matching the problem specification. Formula evaluation correctly resolves each operand either as a literal integer or as a cell lookup, so every formula computes the exact sum required.

Python Solution

class Spreadsheet:

    def __init__(self, rows: int):
        self.cells: dict[str, int] = {}

    def setCell(self, cell: str, value: int) -> None:
        self.cells[cell] = value

    def resetCell(self, cell: str) -> None:
        self.cells.pop(cell, None)

    def _evaluate_operand(self, operand: str) -> int:
        if operand[0].isdigit():
            return int(operand)
        return self.cells.get(operand, 0)

    def getValue(self, formula: str) -> int:
        expression = formula[1:]
        left, right = expression.split('+')

        return (
            self._evaluate_operand(left)
            + self._evaluate_operand(right)
        )

# 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)

The implementation uses a dictionary named cells to store spreadsheet values.

The constructor ignores the rows parameter because the problem guarantees all cell references used later will be valid. Since unspecified cells are always treated as 0, no grid allocation is necessary.

The setCell method inserts or updates the value associated with a cell reference.

The resetCell method removes the cell from the dictionary. Using pop(cell, None) avoids errors if the cell is already absent.

The helper method _evaluate_operand determines whether an operand is an integer literal or a cell reference. Numeric operands are converted with int(), while cell references are retrieved from the dictionary using a default value of 0.

The getValue method removes the leading '=', splits around '+', evaluates both operands, and returns their sum.

Go Solution

type Spreadsheet struct {
	cells map[string]int
}

func Constructor(rows int) Spreadsheet {
	return Spreadsheet{
		cells: make(map[string]int),
	}
}

func (this *Spreadsheet) SetCell(cell string, value int) {
	this.cells[cell] = value
}

func (this *Spreadsheet) ResetCell(cell string) {
	delete(this.cells, cell)
}

func (this *Spreadsheet) evaluateOperand(operand string) int {
	if operand[0] >= '0' && operand[0] <= '9' {
		value := 0
		for _, ch := range operand {
			value = value*10 + int(ch-'0')
		}
		return value
	}

	if value, exists := this.cells[operand]; exists {
		return value
	}
	return 0
}

func (this *Spreadsheet) GetValue(formula string) int {
	expression := formula[1:]

	plusIndex := 0
	for expression[plusIndex] != '+' {
		plusIndex++
	}

	left := expression[:plusIndex]
	right := expression[plusIndex+1:]

	return this.evaluateOperand(left) + this.evaluateOperand(right)
}

/**
 * Your Spreadsheet object will be instantiated and called as such:
 * obj := Constructor(rows)
 * obj.SetCell(cell, value)
 * obj.ResetCell(cell)
 * param_3 := obj.GetValue(formula)
 */

The Go implementation mirrors the Python approach. A map[string]int stores cell values, and delete() removes cells during reset operations.

For operand parsing, Go does not provide implicit integer conversion, so the code manually parses numeric strings. Since all values are small and bounded by the constraints, standard int arithmetic is completely safe.

Worked Examples

Example 1

Spreadsheet(3)

Initial state:

Cell Map
{}

Operation:

getValue("=5+7")

Left	Right	Result
5	7	12

Returned value:

State remains:

Cell Map
{}

Operation:

setCell("A1", 10)

State:

Cell Map
{"A1": 10}

Operation:

getValue("=A1+6")

Operand	Value
A1	10
6	6

Result:

10 + 6 = 16

Operation:

setCell("B2", 15)

State:

Cell Map
{"A1": 10, "B2": 15}

Operation:

getValue("=A1+B2")

Operand	Value
A1	10
B2	15

Result:

Operation:

resetCell("A1")

State:

Cell Map
{"B2": 15}

Operation:

getValue("=A1+B2")

Operand	Value
A1	0
B2	15

Result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Hash map operations and formula parsing involve only a constant amount of work
Space	O(k)	Stores only cells currently present in the map

The formula always contains exactly two operands and one plus sign, so parsing never depends on the spreadsheet size. Hash map lookups, insertions, and deletions are average-case constant time. Therefore every operation runs in O(1) time. The storage requirement depends only on the number of cells currently stored, denoted by k.

Test Cases

# Example from problem statement
s = Spreadsheet(3)
assert s.getValue("=5+7") == 12  # both operands are integers
s.setCell("A1", 10)
assert s.getValue("=A1+6") == 16  # cell + integer
s.setCell("B2", 15)
assert s.getValue("=A1+B2") == 25  # cell + cell
s.resetCell("A1")
assert s.getValue("=A1+B2") == 15  # reset cell becomes 0

# Uninitialized cells
s = Spreadsheet(10)
assert s.getValue("=A1+B1") == 0  # both cells unset

# Single cell and integer
s = Spreadsheet(10)
s.setCell("Z10", 123)
assert s.getValue("=Z10+7") == 130  # multi-digit row reference

# Reset existing cell
s = Spreadsheet(10)
s.setCell("A1", 50)
s.resetCell("A1")
assert s.getValue("=A1+0") == 0  # reset removes value

# Overwrite value
s = Spreadsheet(10)
s.setCell("A1", 10)
s.setCell("A1", 25)
assert s.getValue("=A1+5") == 30  # latest assignment wins

# Large values
s = Spreadsheet(1000)
s.setCell("Z1000", 100000)
assert s.getValue("=Z1000+100000") == 200000  # constraint maximums

# Mixed unset and set cell
s = Spreadsheet(100)
s.setCell("C5", 40)
assert s.getValue("=C5+D5") == 40  # unset cell contributes 0

# Integer only formula with zero
s = Spreadsheet(1)
assert s.getValue("=0+0") == 0  # smallest values

# Multiple resets
s = Spreadsheet(10)
s.resetCell("A1")
s.resetCell("A1")
assert s.getValue("=A1+5") == 5  # repeated reset remains safe

Test Summary

Test	Why
Problem example	Verifies all required operations together
Uninitialized cells	Confirms default value is 0
Multi-digit row reference	Validates parsing of larger row numbers
Reset existing cell	Confirms deletion behavior
Overwrite value	Ensures latest assignment replaces old value
Maximum values	Tests upper constraint limits
Set plus unset cell	Verifies default lookup behavior
Zero formula	Tests smallest valid values
Multiple resets	Ensures reset is idempotent

Edge Cases

Referencing a Cell That Was Never Assigned

A common mistake is assuming every referenced cell already exists in storage. The problem explicitly states that unset cells should be treated as 0. The implementation handles this by using dictionary or map lookups with a default value of 0. Therefore, expressions such as "=A1+B1" work correctly even when neither cell has ever been assigned.

Resetting an Already Empty Cell

A reset operation may be called on a cell that is not currently stored. An implementation that blindly deletes without checking could potentially cause errors in some languages. The solution uses safe removal operations, pop(..., None) in Python and delete() in Go, both of which succeed even when the key is absent.

Multi-Digit Row Numbers

Cell references are not limited to a single-digit row index. References such as "A1000" and "Z999" are valid. A fragile parser might incorrectly assume the row number consists of only one character. This solution never attempts to separate column and row components because the entire cell reference string is used directly as the hash map key, making multi-digit row numbers naturally supported.

Cells Updated Multiple Times

A cell may receive multiple assignments before being queried. The spreadsheet should always use the most recent value. Since the hash map stores exactly one value per key, every new setCell operation overwrites the previous entry, guaranteeing that future formula evaluations use the latest value.