NeetCode #175LC-631HardArrays & Hashing
← Back to All Problems#175 · #631 · Design Excel Sum Formula(设计 Excel 求和公式)
📌 Problem Statement & Constraints
Design a simplified Excel with
set(row, column, val), get(row, column) and sum(row, column, numbers) where numbers is a list of cell references or ranges like "A1:B2". Columns are letters starting at A and rows start at 1. Sum cells must reflect later updates to their inputs. Constraints: 1 <= height <= 26, 1 <= width <= 26; at most 10^4 calls.💡 Core Algorithmic Approaches
- Store the raw grid values in a 2D array, and store formulas separately as a map from cell to a list of rectangles.
getchecks whether the cell has a formula: if so, recursively sum the referenced cells; otherwise return the stored value.setwrites the value and clears any formula at that cell.sumrecords the rectangles and returns the freshly evaluated total, so the formula's value always reflects the current grid -- which is what makes later updates propagate.
💻 Benchmark Python3 Implementation
class Excel:
def __init__(self, height: int, width: int):
self.grid = [[0] * (width + 1) for _ in range(height + 1)] # 1-indexed
self.formulas = {} # (r, c) -> list of (r1, c1, r2, c2)
def _parse(self, ref: str):
col = 0
i = 0
while i < len(ref) and ref[i].isalpha():
col = col * 26 + (ord(ref[i]) - ord("A") + 1)
i += 1
return int(ref[i:]), col
def set(self, row: int, column: int, val: int) -> None:
self.grid[row][column] = val
self.formulas.pop((row, column), None) # a value overwrites any formula
def get(self, row: int, column: int) -> int:
if (row, column) not in self.formulas:
return self.grid[row][column]
total = 0
for r1, c1, r2, c2 in self.formulas[(row, column)]:
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
total += self.get(r, c) # recursive evaluation
return total
def sum(self, row: int, column: int, numbers: List[str]) -> int:
rects = []
for n in numbers:
if ":" in n:
a, b = n.split(":")
r1, c1 = self._parse(a)
r2, c2 = self._parse(b)
else:
r1, c1 = self._parse(n)
r2, c2 = r1, c1
rects.append((r1, c1, r2, c2))
self.formulas[(row, column)] = rects
return self.get(row, column)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(cells referenced) per get or sum, since evaluation is recursive over the referenced ranges. With a 26x26 grid the ranges are small.
💾 Space Complexity
O(height * width) for the grid plus the stored formulas.
⚠️ Interview Pitfalls & Follow-ups
- Caching the sum value instead of the formula: later updates to the inputs would not be reflected, which the problem explicitly requires.
- Forgetting to clear the formula on
set: the cell would keep returning its old formula's value. - Parsing the column letters as a simple ordinal:
A=1,Z=26, butAA=27, so the base-26 accumulation is required. - Using 0-based indices internally: the API is 1-based for rows and 1-based for columns, so the grid is allocated with padding.
- Not handling single-cell references in
sum:"A1"has no colon and must be treated as a 1x1 range.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.