Problem

A spreadsheet is a grid with 26 columns (labeled from 'A' to 'Z') and a given number of rows. Each cell in the spreadsheet can hold an integer value between 0 and 105.

Implement the Spreadsheet class:

  • Spreadsheet(int rows) Initializes a spreadsheet with 26 columns (labeled 'A' to 'Z') and the specified number of rows. All cells are initially set to 0.
  • void setCell(String cell, int value) Sets the value of the specified cell. The cell reference is provided in the format "AX" (e.g., "A1", "B10"), where the letter represents the column (from 'A' to 'Z') and the number represents a 1-indexed row.
  • void resetCell(String cell) Resets the specified cell to 0.
  • int getValue(String formula) Evaluates a formula of the form "=X+Y", where X and Y are either cell references or non-negative integers, and returns the computed sum.

Note: If getValue references a cell that has not been explicitly set using setCell, its value is considered 0.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Input:  
["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue",
"resetCell", "getValue"]  
[[3], ["=5+7"], ["A1", 10], ["=A1+6"], ["B2", 15], ["=A1+B2"], ["A1"],
["=A1+B2"]]
Output:  
[null, 12, null, 16, null, 25, null, 15]
**Explanation**
Spreadsheet spreadsheet = new Spreadsheet(3); // Initializes a spreadsheet
with 3 rows and 26 columns  
spreadsheet.getValue("=5+7"); // returns 12 (5+7)  
spreadsheet.setCell("A1", 10); // sets A1 to 10  
spreadsheet.getValue("=A1+6"); // returns 16 (10+6)  
spreadsheet.setCell("B2", 15); // sets B2 to 15  
spreadsheet.getValue("=A1+B2"); // returns 25 (10+15)  
spreadsheet.resetCell("A1"); // resets A1 to 0  
spreadsheet.getValue("=A1+B2"); // returns 15 (0+15)

Constraints

  • 1 <= rows <= 10^3
  • 0 <= value <= 10^5
  • The formula is always in the format "=X+Y", where X and Y are either valid cell references or non-negative integers with values less than or equal to 105.
  • Each cell reference consists of a capital letter from 'A' to 'Z' followed by a row number between 1 and rows.
  • At most 104 calls will be made in total to setCell, resetCell, and getValue.

Solution

Method 1 – 2D Array and Simple Parsing

Intuition

We can use a 2D array to represent the spreadsheet, mapping columns ‘A’-‘Z’ to indices 0-25 and rows to indices 0-based. For formulas, we parse the operands and check if they are cell references or integers, then sum their values.

Approach

  1. Use a 2D array mat of size rows x 26 to store cell values, initialized to 0.
  2. For setCell(cell, value), parse the column and row, and set the value in mat.
  3. For resetCell(cell), set the corresponding cell to 0.
  4. For getValue(formula), parse the formula (always in the form =X+Y). For each operand, if it is a cell reference, get its value from mat; if it is an integer, parse it directly. Return the sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Spreadsheet {
    vector<vector<int>> mat;
    int rows;
    int colIdx(char c) { return c - 'A'; }
    pair<int, int> parseCell(const string& cell) {
        int col = colIdx(cell[0]);
        int row = stoi(cell.substr(1)) - 1;
        return {row, col};
    }
    int getVal(const string& s) {
        if (isalpha(s[0])) {
            auto [r, c] = parseCell(s);
            return mat[r][c];
        } else {
            return stoi(s);
        }
    }
public:
    Spreadsheet(int r) : rows(r), mat(r, vector<int>(26, 0)) {}
    void setCell(string cell, int value) {
        auto [row, col] = parseCell(cell);
        mat[row][col] = value;
    }
    void resetCell(string cell) {
        auto [row, col] = parseCell(cell);
        mat[row][col] = 0;
    }
    int getValue(string formula) {
        string x, y;
        int eq = formula.find('=');
        int plus = formula.find('+');
        x = formula.substr(eq+1, plus-eq-1);
        y = formula.substr(plus+1);
        return getVal(x) + getVal(y);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Spreadsheet {
    private int[][] mat;
    private int rows;
    public Spreadsheet(int rows) {
        this.rows = rows;
        mat = new int[rows][26];
    }
    private int[] parseCell(String cell) {
        int col = cell.charAt(0) - 'A';
        int row = Integer.parseInt(cell.substring(1)) - 1;
        return new int[]{row, col};
    }
    private int getVal(String s) {
        if (Character.isLetter(s.charAt(0))) {
            int[] rc = parseCell(s);
            return mat[rc[0]][rc[1]];
        } else {
            return Integer.parseInt(s);
        }
    }
    public void setCell(String cell, int value) {
        int[] rc = parseCell(cell);
        mat[rc[0]][rc[1]] = value;
    }
    public void resetCell(String cell) {
        int[] rc = parseCell(cell);
        mat[rc[0]][rc[1]] = 0;
    }
    public int getValue(String formula) {
        int eq = formula.indexOf('=');
        int plus = formula.indexOf('+');
        String x = formula.substring(eq+1, plus);
        String y = formula.substring(plus+1);
        return getVal(x) + getVal(y);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Spreadsheet:
    def __init__(self, rows: int):
        self.mat = [[0]*26 for _ in range(rows)]
    def _parse_cell(self, cell: str) -> tuple[int, int]:
        col = ord(cell[0]) - ord('A')
        row = int(cell[1:]) - 1
        return row, col
    def _get_val(self, s: str) -> int:
        if s[0].isalpha():
            r, c = self._parse_cell(s)
            return self.mat[r][c]
        else:
            return int(s)
    def setCell(self, cell: str, value: int) -> None:
        r, c = self._parse_cell(cell)
        self.mat[r][c] = value
    def resetCell(self, cell: str) -> None:
        r, c = self._parse_cell(cell)
        self.mat[r][c] = 0
    def getValue(self, formula: str) -> int:
        eq = formula.find('=')
        plus = formula.find('+')
        x = formula[eq+1:plus]
        y = formula[plus+1:]
        return self._get_val(x) + self._get_val(y)

Complexity

  • ⏰ Time complexity: O(1) per operation, as all operations are direct array accesses and simple parsing.
  • 🧺 Space complexity: O(rows*26), for the spreadsheet matrix.