LeetCode 631: Design Excel Sum Formula Solution in Python – A Step-by-Step Guide

What Is LeetCode 631: Design Excel Sum Formula?

In LeetCode 631: Design Excel Sum Formula, you’re tasked with implementing an Excel class with a grid of cells (rows 1 to H, columns A to W) and three methods:

• set(row, col, val): Set a value in a cell.
• get(row, col): Return the value in a cell (computed if it’s a formula).
• sum(row, col, formulas): Set a cell to compute the sum of ranges (e.g., "A1:A3"), updating dynamically.

Cells can hold integers or sum formulas (e.g., ["A1", "B2:C3"]), and when a cell’s value changes, all dependent sums recompute. For example, setting A1 to 2 and A2 to a sum of A1 affects A2 when A1 changes. This problem tests your ability to design a system with dependency tracking and dynamic updates.

Problem Statement

• Input:
• H: Integer (height, 1 ≤ H ≤ 26).
• W: Char (width, 'A' to 'W').
• Method calls: set, get, sum with row/col/values/formulas.
• Output: An Excel class implementing the methods.
• Rules:
• Rows: 1 to H, Columns: A to W.
• set: Updates value and dependent sums.
• get: Returns current value (computed for sums).
• sum: Sets a formula, returns computed sum.

Constraints

• 1 ≤ H ≤ 26.
• 'A' ≤ W ≤ 'W'.
• -10⁹ ≤ val ≤ 10⁹.
• Up to 10⁵ method calls.

Examples

• Input:
• ["Excel","set","set","sum","set","get"]
• [[3,'C'],[1,'A',2],[2,'A',3],[2,'B',["A1","A2"]],[1,'A',5],[2,'B']]
• Output: [null,null,null,5,null,8]
• Init 3xC, A1=2, A2=3, B2=sum(A1,A2)=5, A1=5, B2=8.
• Input:
• ["Excel","set","get"]
• [[1,'A'],[1,'A',10],[1,'A']]
• Output: [null,null,10]

These examples show the dynamics—let’s solve it!

Understanding the Problem: Designing Excel

To solve LeetCode 631: Design Excel Sum Formula in Python, we need to design a class that tracks cell values and formulas, updates sums when dependencies change, and handles grid coordinates (e.g., "A1"). A naive approach might recompute everything per call, but we need efficiency for 10⁵ calls. We’ll use:

• Best Solution (Array-Based with Dependency Tracking): O(HW + F) time per update, O(HW) space—fast and practical (F = formula cells).
• Alternative Solution (Graph-Based with DFS): O(HW) time per update, O(HW) space—flexible but complex.

Let’s start with the array-based solution, breaking it down for beginners.

Best Solution: Array-Based with Dependency Tracking

Why This Is the Best Solution

The array-based approach with dependency tracking is the top choice for LeetCode 631 because it’s efficient—O(HW + F) time for updates with O(HW) space—and balances simplicity with performance. It uses a grid to store values/formulas and a reverse dependency map to update only affected cells, fitting constraints (H ≤ 26, W ≤ 'W'). It’s like a smart spreadsheet that knows who depends on whom!

How It Works

Think of this as a spreadsheet manager:

• Step 1: Initialize Grid:
• 2D array for values/formulas, reverse dependency map.
• Step 2: Set Value:
• Update cell, notify dependents via map, recompute sums.
• Step 3: Get Value:
• Return cell value (compute if formula).
• Step 4: Set Sum Formula:
• Parse ranges, store formula, compute initial sum, update dependencies.
• Step 5: Update Dependents:
• Recursively recompute dependent sums.

It’s like a dynamic spreadsheet—track and update!

Step-by-Step Example

Example: H=3, W='C', Operations: set(1,'A',2), set(2,'A',3), sum(2,'B',["A1","A2"]), set(1,'A',5)

• Step 1: Init:
• Grid: 3x3 ([[0,0,0], [0,0,0], [0,0,0]]).
• Deps: {}.
• Step 2: set(1, 'A', 2):
• Grid[0][0] = 2, no deps yet.
• Step 3: set(2, 'A', 3):
• Grid[1][0] = 3.
• Step 4: sum(2, 'B', ["A1", "A2"]):
• Grid[1][1] = (["A1", "A2"], 5) (2 + 3).
• Deps: {(0,0): [(1,1)], (1,0): [(1,1)]}.
• Step 5: set(1, 'A', 5):
• Grid[0][0] = 5.
• Update (1,1): New sum = 5 + 3 = 8.
• Grid[1][1] = (["A1", "A2"], 8).
• Step 6: get(2, 'B'): Return 8.
• Output: [null, null, null, 5, null, 8].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Excel:
    def __init__(self, H: int, W: str):
        # Step 1: Initialize grid and dependency map
        self.H = H
        self.W = ord(W) - ord('A') + 1  # Convert W to index (e.g., 'C' -> 3)
        self.grid = [[0] * self.W for _ in range(H)]  # Values or (formula, value)
        self.deps = {}  # (r,c) -> list of dependent (r,c)

    def set(self, row: int, col: str, val: int) -> None:
        # Step 2: Set value and update dependents
        r, c = row - 1, ord(col) - ord('A')
        self.grid[r][c] = val  # Set as integer, not formula
        # Update all dependent cells
        self._update_dependents(r, c)

    def get(self, row: int, col: str) -> int:
        # Step 3: Get value (compute if formula)
        r, c = row - 1, ord(col) - ord('A')
        if isinstance(self.grid[r][c], int):
            return self.grid[r][c]
        formula, value = self.grid[r][c]
        return value  # Return precomputed value

    def sum(self, row: int, col: str, formulas: List[str]) -> int:
        # Step 4: Set sum formula and compute
        r, c = row - 1, ord(col) - ord('A')
        # Parse ranges and build dependency
        cells = set()
        for formula in formulas:
            start, end = formula.split(':') if ':' in formula else (formula, formula)
            r1, c1 = int(start[1:]) - 1, ord(start[0]) - ord('A')
            r2, c2 = int(end[1:]) - 1, ord(end[0]) - ord('A')
            for i in range(r1, r2 + 1):
                for j in range(c1, c2 + 1):
                    cells.add((i, j))
                    if (i, j) not in self.deps:
                        self.deps[(i, j)] = []
                    self.deps[(i, j)].append((r, c))

        # Compute initial sum
        total = sum(self.get(i + 1, chr(j + ord('A'))) for i, j in cells)
        self.grid[r][c] = (formulas, total)
        return total

    def _update_dependents(self, r: int, c: int) -> None:
        # Step 5: Update all cells dependent on (r, c)
        if (r, c) in self.deps:
            for dr, dc in self.deps[(r, c)]:
                if isinstance(self.grid[dr][dc], tuple):
                    formula, _ = self.grid[dr][dc]
                    new_val = self.sum(dr + 1, chr(dc + ord('A')), formula)
                    self.grid[dr][dc] = (formula, new_val)

• Lines 4-7: Init grid and deps map.
• Lines 10-14: set: Update cell, trigger dependent updates.
• Lines 17-23: get: Return value, compute if formula.
• Lines 26-42: sum: Parse ranges, set formula, compute sum, update deps.
• Lines 45-50: _update_dependents: Recursively update dependent sums.
• Time Complexity: O(HW + F) per update—F is formula-affected cells.
• Space Complexity: O(HW)—grid and deps.

This is like a spreadsheet engine—fast and dynamic!

Alternative Solution: Graph-Based with DFS

Why an Alternative Approach?

The graph-based approach with DFS models cells as nodes and dependencies as edges—O(HW) time per update, O(HW) space. It’s more flexible, explicitly tracking dependency graphs, but complex and less efficient for updates. It’s like mapping a network of formula connections!

How It Works

Picture this as a dependency network:

• Step 1: Init grid and graph.
• Step 2: Set: Update value, DFS to recompute dependents.
• Step 3: Get: DFS to compute value if formula.
• Step 4: Sum: Build graph edges, compute initial sum.
• Step 5: Return result.

It’s like a graph navigator—track and compute!

Step-by-Step Example

Example: Same as above

• Init: Grid, Graph = {}.
• Set A1=2: Grid[0][0] = 2.
• Set A2=3: Grid[1][0] = 3.
• Sum B2=["A1","A2"]: Graph[B2] = [A1, A2], compute 5.
• Set A1=5: DFS updates B2 to 8.

Code for Graph Approach

Copy codeclass Excel:
    def __init__(self, H: int, W: str):
        self.H = H
        self.W = ord(W) - ord('A') + 1
        self.grid = [[0] * self.W for _ in range(H)]
        self.graph = {}  # (r,c) -> list of dependent (r,c)
        self.formulas = {}  # (r,c) -> list of formula strings

    def set(self, row: int, col: str, val: int) -> None:
        r, c = row - 1, ord(col) - ord('A')
        self.grid[r][c] = val
        if (r, c) in self.formulas:
            del self.formulas[(r, c)]  # Clear formula if set to value
        self._dfs(r, c)

    def get(self, row: int, col: str) -> int:
        r, c = row - 1, ord(col) - ord('A')
        if (r, c) not in self.formulas:
            return self.grid[r][c]
        return self._compute_sum(r, c)

    def sum(self, row: int, col: str, formulas: List[str]) -> int:
        r, c = row - 1, ord(col) - ord('A')
        cells = set()
        for formula in formulas:
            start, end = formula.split(':') if ':' in formula else (formula, formula)
            r1, c1 = int(start[1:]) - 1, ord(start[0]) - ord('A')
            r2, c2 = int(end[1:]) - 1, ord(end[0]) - ord('A')
            for i in range(r1, r2 + 1):
                for j in range(c1, c2 + 1):
                    cells.add((i, j))
                    if (i, j) not in self.graph:
                        self.graph[(i, j)] = []
                    self.graph[(i, j)].append((r, c))
        self.formulas[(r, c)] = formulas
        value = self._compute_sum(r, c)
        self.grid[r][c] = value
        return value

    def _compute_sum(self, r: int, c: int) -> int:
        if (r, c) not in self.formulas:
            return self.grid[r][c]
        total = 0
        for formula in self.formulas[(r, c)]:
            start, end = formula.split(':') if ':' in formula else (formula, formula)
            r1, c1 = int(start[1:]) - 1, ord(start[0]) - ord('A')
            r2, c2 = int(end[1:]) - 1, ord(end[0]) - ord('A')
            for i in range(r1, r2 + 1):
                for j in range(c1, c2 + 1):
                    total += self.get(i + 1, chr(j + ord('A')))
        return total

    def _dfs(self, r: int, c: int) -> None:
        if (r, c) in self.graph:
            for dr, dc in self.graph[(r, c)]:
                if (dr, dc) in self.formulas:
                    self.grid[dr][dc] = self._compute_sum(dr, dc)
                    self._dfs(dr, dc)

• Lines 6-8: Init grid and graph.
• Lines 11-15: set: Update, clear formula, DFS.
• Lines 18-22: get: Compute if formula.
• Lines 25-41: sum: Build graph, compute sum.
• Lines 44-55: _compute_sum: DFS sum computation.
• Lines 58-63: _dfs: Update dependents.
• Time Complexity: O(HW) per update—DFS traversal.
• Space Complexity: O(HW)—graph and formulas.

It’s a graph spreadsheet—flexible but complex!

Comparing the Two Solutions

• Array-Based (Best):
• Pros: O(HW + F) time, O(HW) space, fast and practical.
• Cons: Less flexible for complex dependencies.
• Graph-Based (Alternative):
• Pros: O(HW) time, O(HW) space, explicit graph.
• Cons: More complex, slower updates.

Array-based wins for efficiency.

Additional Examples and Edge Cases

• Input: set(1,'A',1), sum(1,'B',["A1"]) → [null, 1].
• Input: Empty grid → All gets return 0.

Both handle these well.

Complexity Breakdown

• Array-Based: Time O(HW + F), Space O(HW).
• Graph-Based: Time O(HW), Space O(HW).

Array-based is practical.

Key Takeaways

• Array-Based: Dependency tracking—smart!
• Graph-Based: DFS navigation—clear!
• Design: Spreadsheets are fun.
• Python Tip: Dicts rock—see Python Basics.

Final Thoughts: Build That Spreadsheet

LeetCode 631: Design Excel Sum Formula in Python is a challenging design puzzle. Array-based tracking offers speed and clarity, while graph-based DFS provides flexibility. Want more? Try LeetCode 146: LRU Cache or LeetCode 208: Implement Trie. Ready to compute? Head to Solve LeetCode 631 on LeetCode and design that Excel today!