⚡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