⚡Flashcard Drill➔
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

  1. Store the raw grid values in a 2D array, and store formulas separately as a map from cell to a list of rectangles.
  2. get checks whether the cell has a formula: if so, recursively sum the referenced cells; otherwise return the stored value.
  3. set writes the value and clears any formula at that cell.
  4. sum records 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, but AA=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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems

中文速览与面试要点

设计 Excel 求和公式

请你设计一个 Excel 类: __init__(height, width) 初始化一个 height × width 的表格,所有单元格初值为 0,列用大写字母 A、B、C… 表示,行用 1、2、3… 表示。 set(row, column, val) 把单元格设为数值 val。 get(row, column) 返回单元格的值(若该单元格是求和公式则返回计算结果)。 sum(row, column, numbers) 把单元格设为求和公式,numbers 是形如 ["A1", "B1:C2"] 的字符串列表(可含单个单元格或矩形区域),返回计算结果。约束:1 ≤ height ≤ 26;1 ≤ width ≤ 26;numbers 中每一项都合法;最多调用 10^4 次方法。

核心要点

  • 二维数组存值 + 字典存公式(标准解) : vals[r][c] 存数值, formulas[(r, c)] 存该单元格的求和范围列表。
  • set 时清除公式 :把单元格设为数值时,必须同时删除它原有的公式(否则 get 会走公式分支)。
  • get 时递归求值 :若单元格是公式,遍历其所有范围,对范围内每个单元格递归调用 get 并累加。
  • 解析单元格坐标 :把 "B3" 解析为 (row=3, col=2) 。列字母按 26 进制转换(A=1、B=2、…、Z=26)。
  • 解析范围 : "B1:C2" 拆成两个单元格坐标,取 min/max 得到矩形范围(题目不保证顺序,需归一化)。
  • 为什么递归能正确工作 :Excel 的依赖关系构成有向无环图(题目保证无循环引用),因此递归求值必然终止。

常见陷阱

  • set 时不清除原有公式 :会导致 get 仍然走公式分支,返回旧公式的结果而非新设的值。这是本题最常见的错误。
  • 列字母按 0-based 解析 : "A" 应映射到列 1,不是 0。公式是 col = col * 26 + (ord(ch) - ord("A") + 1) 。
  • 范围 "B2:A1" 不做归一化 :题目不保证范围的两端有序,必须用 min/max 归一化,否则 range(r1, r2+1) 会得到空区间。
  • 忘记递归求值 :公式引用的单元格本身可能也是公式,必须递归调用 get 而非直接读 vals 。
  • 误以为需要处理循环引用 :题目保证不会出现循环引用(依赖图无环),因此递归必然终止。

参考实现

class Excel:
    def __init__(self, height: int, width: int):
        self.h = height
        self.w = width
        # 值表(下标 1..height / 1..width)
        self.vals = [[0] * (width + 1) for _ in range(height + 1)]
        self.formulas = {}      # (row, col) -> [(r1, c1, r2, c2), ...]

    def _parse(self, cell: str) -> tuple:
        """把 "B3" 解析为 (row, col),均为 1-based。"""
        i = 0
        col = 0
        while i < len(cell) and cell[i].isalpha():
            col = col * 26 + (ord(cell[i]) - ord('A') + 1)
            i += 1
        return int(cell[i:]), col

    def set(self, row: int, column: int, val: int) -> None:
        self.formulas.pop((row, column), None)   # 关键:清除原有公式
        self.vals[row][column] = val

    def get(self, row: int, column: int) -> int:
        if (row, column) in self.formulas:
            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)   # 递归求值
            return total
        return self.vals[row][column]

    def sum(self, row: int, column: int, numbers: list[str]) -> int:
        ranges = []
        for item in numbers:
            if ':' in item:
                a, b = item.split(':')
                r1, c1 = self._parse(a)
                r2, c2 = self._parse(b)
                # 归一化,保证 r1 <= r2、c1 <= c2
                ranges.append((min(r1, r2), min(c1, c2), max(r1, r2), max(c1, c2)))
            else:
                r1, c1 = self._parse(item)
                ranges.append((r1, c1, r1, c1))
        self.formulas[(row, column)] = ranges
        return self.get(row, column)