LeetCode Solutions Blog

Design Spreadsheet

Number: 3797

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Design a simple spreadsheet with 26 fixed columns (labeled A to Z) and a specified number of rows, where each cell holds an integer between 0 and 10^5. Implement a class that supports setting a cell’s value, resetting a cell to 0, and evaluating formulas of the form "=X+Y" (where X and Y can be either integers or cell references). If a cell is never explicitly set, its value is considered 0.

Key Insights

Use a 2D array (or equivalent) to represent the spreadsheet.
Convert column letters (A-Z) to an index (0-25) and adjust row numbers from 1-indexed to 0-indexed.
Parse the formula by removing the "=" and splitting based on "+".
Differentiate between numeric constants and cell references using character checks.
Direct access operations (set, reset, and get) can be done in constant time.

Space and Time Complexity

Time Complexity:

setCell and resetCell operations: O(1)
getValue operation: O(1) (given fixed-format formulas and constant-time parsing) Space Complexity:
O(rows * 26) for storing the spreadsheet cells

Solution

We use a 2D array (or equivalent) to store cell values. Each cell is accessed by converting its cell reference (like "A1") into 0-indexed row and column indices. The getValue method parses the formula by stripping the leading "=" and splitting by "+". For each operand, we check if it starts with a digit (and treat it as an integer) or a letter (and look up the corresponding cell value). This straightforward approach ensures O(1) operations for each method call.

Code Solutions

class Spreadsheet:
    def __init__(self, rows):
        # Initialize a grid with rows and 26 columns (A-Z) set to 0.
        self.rows = rows
        self.cols = 26
        self.sheet = [[0] * self.cols for _ in range(rows)]
    
    def convert_cell(self, cell):
        # Convert a cell reference (e.g., "A1") to 0-indexed row and column indices.
        col = ord(cell[0]) - ord('A')
        row = int(cell[1:]) - 1
        return row, col
    
    def setCell(self, cell, value):
        # Set the specified cell to the given value.
        row, col = self.convert_cell(cell)
        self.sheet[row][col] = value
    
    def resetCell(self, cell):
        # Reset the specified cell to 0.
        row, col = self.convert_cell(cell)
        self.sheet[row][col] = 0
    
    def getValue(self, formula):
        # Remove the "=" and split the formula into its two parts.
        expr = formula[1:]
        part1, part2 = expr.split('+')
        
        # Helper function to determine the value of an operand.
        def get_operand(operand):
            if operand[0].isdigit():
                return int(operand)
            else:
                r, c = self.convert_cell(operand)
                return self.sheet[r][c]
        
        return get_operand(part1) + get_operand(part2)

# Example usage:
if __name__ == "__main__":
    spreadsheet = Spreadsheet(3)
    print(spreadsheet.getValue("=5+7"))   # Output: 12
    spreadsheet.setCell("A1", 10)
    print(spreadsheet.getValue("=A1+6"))   # Output: 16
    spreadsheet.setCell("B2", 15)
    print(spreadsheet.getValue("=A1+B2"))  # Output: 25
    spreadsheet.resetCell("A1")
    print(spreadsheet.getValue("=A1+B2"))  # Output: 15