Facebook Pixel

3484. Design Spreadsheet

MediumDesignArrayHash TableStringMatrix
Leetcode Link

Problem Description

A spreadsheet is structured as a grid with 26 columns labeled from 'A' to 'Z' and a specified number of rows. Each cell can store an integer value ranging from 0 to (10^5).

You'll be implementing the Spreadsheet class that should provide the following functionalities:

  • Initialization: Spreadsheet(int rows) - This sets up a spreadsheet with 26 columns and the specified number of rows. Initially, every cell is set to 0.
  • Set Cell Value: void setCell(String cell, int value) - Sets a particular cell (denoted like "A1", "B10") to a specific integer value.
  • Reset Cell Value: void resetCell(String cell) - This action resets the value of a specific cell back to 0.
  • Evaluate Formula: int getValue(String formula) - Calculates a formula represented like "=X+Y", where X and Y can be cell references or non-negative integers, and returns the calculated sum.

If getValue references a cell that hasn't been explicitly set using setCell, that cell's value defaults to 0.

Intuition

This problem requires managing and manipulating cell values in a spreadsheet format. The intuitive approach involves using a dictionary, d, to efficiently store and access the values of the cells based on their references, which serve as keys.

  • Set Cell: For setting the value of a cell, simply associate the cell's reference with its value in the dictionary.
  • Reset Cell: Resetting involves removing the cell reference from the dictionary, or setting its value to 0, to reflect a reset.
  • Evaluate Formula: For formulas, split the equation into components by '+'. Determine whether each component is an integer or a cell reference. If it's a reference, fetch its value from the dictionary (default to 0 if unset). Sum up these values to get the result.

This solution effectively uses a hash table for optimal look-up operations, ensuring that both setting and accessing cell values are efficient.

Solution Approach

The solution employs a hash table, represented by a dictionary d in the code, to store the values of spreadsheet cells. Here’s how the solution works step-by-step:

  1. Initialization:

    • When we initialize the Spreadsheet with a specified number of rows, a dictionary d is created to hold cell values. Each cell is initially set to 0, but only modified cells are stored in d.
  2. Setting a Cell Value:

    • The setCell method takes a cell reference (e.g., "A1") and a value, storing them in the dictionary with the cell reference as the key. This allows quick access and update operations.
    def setCell(self, cell: str, value: int) -> None:
        self.d[cell] = value
  3. Resetting a Cell:

    • The resetCell function removes the specified cell from the dictionary using pop. If the cell isn’t in the dictionary, None ensures no error occurs.
    def resetCell(self, cell: str) -> None:
        self.d.pop(cell, None)
  4. Evaluating a Formula:

    • The getValue method handles formulas in the format =X+Y, where X and Y can be a mix of cell references or direct integers. It processes the formula by:
      • Removing the "=" and splitting by "+" to identify components.
      • For each component, checks if it is a digit. If so, it adds its integer value to the result.
      • If it's not a digit, it retrieves the value from the dictionary, defaulting to 0 if the cell hasn’t been set, and adds it to the result.
    def getValue(self, formula: str) -> int:
        ans = 0
        for cell in formula[1:].split("+"):
            ans += int(cell) if cell[0].isdigit() else self.d.get(cell, 0)
        return ans

This approach efficiently handles cell operations and formula evaluations by leveraging the constant-time complexity of dictionary operations for setting, retrieving, and removing data.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Initialize the Spreadsheet

  • Action: Create a spreadsheet with 3 rows.
  • State: d = {} (A dictionary to store cell values that are explicitly set.)

Set Cell Values

  1. Action: setCell("A1", 10)

    • The cell "A1" is set to 10.
    • State: d = {"A1": 10}
  2. Action: setCell("B1", 5)

    • The cell "B1" is set to 5.
    • State: d = {"A1": 10, "B1": 5}

Evaluate a Formula

  • Action: getValue("=A1+B1+3")
    • Formula evaluation involves:
      • Splitting the expression after the "=": components are ["A1", "B1", "3"].
      • Retrieving values:
        • "A1" -> 10 (from d)
        • "B1" -> 5 (from d)
        • "3" -> 3 (as it is a digit)
      • Summing up: 10 + 5 + 3 = 18
    • Result: 18

Reset a Cell

  • Action: resetCell("A1")
    • This removes the entry for "A1" from the dictionary.
    • State: d = {"B1": 5}

Evaluate Another Formula

  • Action: getValue("=A1+B1+5")
    • Formula evaluation involves:
      • Splitting at "+": components are ["A1", "B1", "5"].
      • Retrieving values:
        • "A1" -> 0 (default, because "A1" was reset)
        • "B1" -> 5 (from d)
        • "5" -> 5 (as it is a digit)
      • Summing: 0 + 5 + 5 = 10
    • Result: 10

Solution Implementation

1class Spreadsheet:
2    def __init__(self, rows: int):
3        # Initialize the spreadsheet with a dictionary to store cell values
4        self.cells = {}
5
6    def setCell(self, cell: str, value: int) -> None:
7        # Set the value of the specified cell
8        self.cells[cell] = value
9
10    def resetCell(self, cell: str) -> None:
11        # Reset the specified cell to its default state (i.e., remove it if it exists)
12        self.cells.pop(cell, None)
13
14    def getValue(self, formula: str) -> int:
15        # Calculate the value based on a formula, which is a string of cell references and numbers
16        total = 0
17        # Split the formula by '+' and process each part
18        for component in formula[1:].split("+"):
19            # If the component is a number, add it directly; otherwise, look up its value
20            total += int(component) if component[0].isdigit() else self.cells.get(component, 0)
21        return total
22
23# Your Spreadsheet object will be instantiated and called as such:
24# obj = Spreadsheet(rows)
25# obj.setCell(cell, value)
26# obj.resetCell(cell)
27# param_3 = obj.getValue(formula)
28
1import java.util.HashMap;
2import java.util.Map;
3
4class Spreadsheet {
5    // Map to store cell values where key is the cell identifier like "A1", and value is the integer stored in that cell.
6    private Map<String, Integer> cellMap = new HashMap<>();
7
8    // Constructor to initialize the Spreadsheet with a given number of rows.
9    // 'rows' parameter is not used as there is no direct implementation of row-specific logic.
10    public Spreadsheet(int rows) {
11    }
12
13    // Method to set a value for a specific cell in the spreadsheet.
14    public void setCell(String cell, int value) {
15        cellMap.put(cell, value); // Add or update the cell with the given integer value.
16    }
17
18    // Method to reset a cell, essentially removing its stored value.
19    public void resetCell(String cell) {
20        cellMap.remove(cell); // Remove the cell from the map.
21    }
22
23    // Method to get the result by evaluating a formula.
24    // The formula is expected to be in the format "=A1+B2+12", which requires adding numbers and/or cell values.
25    public int getValue(String formula) {
26        int result = 0;
27
28        // Split the formula by '+' and evaluate each part.
29        for (String cell : formula.substring(1).split("\\+")) {
30            // Check if the part is a direct number or a reference to a cell.
31            if (Character.isDigit(cell.charAt(0))) {
32                result += Integer.parseInt(cell); // Convert number to an integer and add to result.
33            } else {
34                result += cellMap.getOrDefault(cell, 0); // Add the value of the referenced cell or 0 if it doesn't exist.
35            }
36        }
37
38        return result; // Return the computed result.
39    }
40}
41
42/**
43 * Example usage of the Spreadsheet class:
44 * 
45 * Spreadsheet obj = new Spreadsheet(rows);
46 * obj.setCell("A1", 5);
47 * obj.resetCell("A1");
48 * int sum = obj.getValue("=A1+5+B2");
49 */
50
1#include <unordered_map>
2#include <string>
3#include <sstream>
4#include <cctype>
5
6class Spreadsheet {
7private:
8    // Map to hold cell values. Keys are cell identifiers (e.g., "A1"), values are integers.
9    std::unordered_map<std::string, int> cellData;
10
11public:
12    // Constructor to initialize Spreadsheet with a given number of rows.
13    // Currently, it doesn't utilize the 'rows' parameter.
14    Spreadsheet(int rows) {}
15
16    // Method to set the value of a specific cell.
17    void setCell(std::string cell, int value) {
18        cellData[cell] = value;
19    }
20
21    // Method to reset the value of a specific cell, effectively removing it from the map.
22    void resetCell(std::string cell) {
23        cellData.erase(cell);
24    }
25
26    // Method to compute the result of a formula.
27    // The formula is expected to be prefixed with "=" and may contain references to cells or direct integer values.
28    int getValue(std::string formula) {
29        int result = 0; // Initialize result to accumulate values.
30        std::stringstream ss(formula.substr(1)); // Remove the '=' prefix from the formula.
31        std::string cell;
32
33        // Parse the formula and process each part separated by '+'.
34        while (getline(ss, cell, '+')) {
35            if (std::isdigit(cell[0])) {
36                // If the part is a number, convert and add it to the result.
37                result += std::stoi(cell);
38            } else {
39                // If the part is a cell reference, fetch the value if it exists.
40                result += cellData.count(cell) ? cellData[cell] : 0;
41            }
42        }
43        return result; // Return the computed result.
44    }
45};
46
47/**
48 * Your Spreadsheet object will be instantiated and called as such:
49 * Spreadsheet* obj = new Spreadsheet(rows);
50 * obj->setCell(cell, value);
51 * obj->resetCell(cell);
52 * int param_3 = obj->getValue(formula);
53 */
54
1// A Map to store cell names as keys and their respective values as numbers.
2const spreadsheetData: Map<string, number> = new Map<string, number>();
3
4/**
5 * Sets the value of a specific cell.
6 * @param cell - The cell identifier, a string.
7 * @param value - The value to set in the cell, a number.
8 */
9function setCell(cell: string, value: number): void {
10    spreadsheetData.set(cell, value);
11}
12
13/**
14 * Resets (deletes) a specific cell from the spreadsheet.
15 * @param cell - The cell identifier to delete, a string.
16 */
17function resetCell(cell: string): void {
18    spreadsheetData.delete(cell);
19}
20
21/**
22 * Calculates the value of a formula.
23 * @param formula - A formula string which usually starts with '=' and includes cell names and numbers to add.
24 * @returns The computed value based on the formula.
25 */
26function getValue(formula: string): number {
27    let total = 0;
28    // Remove the '=' sign and split the formula by the '+' operator to get each term.
29    const cells = formula.slice(1).split('+');
30  
31    // Iterate over each cell or value in the formula and compute the total.
32    for (const cell of cells) {
33        // Check if the cell is a number or a reference to another cell.
34        total += isNaN(Number(cell)) ? spreadsheetData.get(cell) || 0 : Number(cell);
35    }
36  
37    return total;
38}
39
40/**
41 * Example of usage:
42 * setCell('A1', 5);
43 * setCell('A2', 10);
44 * const result = getValue('=A1+A2+3'); // result will be 18
45 * resetCell('A1');
46 */
47

Time and Space Complexity

The time complexity of the getValue method is O(L), where L is the length of the formula string passed to the method. The reason for this is that the method iterates through the characters of the formula string once, performing operations that depend linearly on the number of cell references and values in the formula.

The space complexity of the getValue method is also O(L). This is because the method splits the formula string into components based on the + symbol, temporarily storing these components. Hence, the space required is proportional to the length of the formula.

Learn more about how to find time and space complexity quickly.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More