Problem Explanation

The problem is about creating a simplified Excel spreadsheet using a 2D array as the backend data structure. The height, H, and the width, W, of the Excel is given at the time of construction where H is a positive integer, and W is an uppercase letter denoting the maximum width of the Excel sheet. The user should be able to set a value to any cell in the spreadsheet by specifying the row and column. Along with that, the user should be able to get the value stored in any cell. Additionally, the program should support the capability to calculate the sum of a list of cells or a range of cells and store the sum in a particular cell.

Walkthrough of an Example

Let's go through a scenario to understand how a solution might look like.

If we create an Excel using Excel(3, 'C'), it means we have an Excel spreadsheet with 3 rows and 3 columns, and all the cells have an initial value of 0.

Copy


   A B C
1 0 0 0
2 0 0 0
3 0 0 0

If we execute Set(1, "A", 2), it means we are setting the cell at row 1, column 'A' to 2.

Copy


   A B C
1 2 0 0
2 0 0 0
3 0 0 0

Solution Explanation

A cell holds either a plain value or a formula. A formula is a sum over other cells, and the same cell can appear in it more than once (for example, ["A1", "A1:B2"] counts A1 twice). The solution stores each formula as a map from referenced cell to the number of times it appears.

Formulas must stay live: after sum(3, "C", ["A1"]), changing A1 must also change C3. Instead of pushing updates to dependent cells, the solution evaluates a formula on demand. get returns the stored value for a plain cell and, for a formula cell, recursively computes count × get(cell) for every referenced cell. The problem guarantees there are no circular references, so the recursion always ends.

The three operations work as follows:

• set(row, column, val) removes any formula at that cell and stores the plain value.
• sum(row, column, numbers) expands every entry (a single cell like "A1" or a range like "A1:B2") into individual cells, counts them, stores the counts as the cell's formula, and returns get(row, column).
• get(row, column) evaluates the cell as described above. Cells that were never set are 0.

For the example Excel(3, "C"), set(1, "A", 2), sum(3, "C", ["A1", "A1:B2"]): the formula for C3 is {A1: 2, B1: 1, A2: 1, B2: 1}, so sum returns 2 × 2 + 0 + 0 + 0 = 4. After set(2, "B", 2), get(3, "C") re-evaluates the formula and returns 4 + 2 = 6.

Each get on a formula cell visits every cell it depends on, directly or indirectly. With at most 26 × 26 cells and few operations, this on-demand evaluation is fast enough.

Python Solution

Copy
from collections import Counter
from typing import List


class Excel:
    def __init__(self, height: int, width: str):
        self.values = {}    # (row, col) -> int, for cells holding a plain value
        self.formulas = {}  # (row, col) -> Counter of referenced cells

    def set(self, row: int, column: str, val: int) -> None:
        key = (row, column)
        self.formulas.pop(key, None)  # A plain value replaces any formula
        self.values[key] = val

    def get(self, row: int, column: str) -> int:
        key = (row, column)
        if key in self.formulas:
            # Evaluate the formula from the current values of its cells
            return sum(count * self.get(r, c) for (r, c), count in self.formulas[key].items())
        return self.values.get(key, 0)

    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        refs = Counter()
        for item in numbers:
            start, _, end = item.partition(':')
            end = end or start
            r1, c1 = int(start[1:]), start[0]
            r2, c2 = int(end[1:]), end[0]
            for r in range(r1, r2 + 1):
                for c in range(ord(c1), ord(c2) + 1):
                    refs[(r, chr(c))] += 1
        self.formulas[(row, column)] = refs
        return self.get(row, column)

JavaScript Solution

Copy
class Excel {
    constructor(height, width) {
        this.values = new Map();   // "row,col" -> number
        this.formulas = new Map(); // "row,col" -> Map of referenced cell -> count
    }

    set(row, column, val) {
        const key = `${row},${column}`;
        this.formulas.delete(key); // A plain value replaces any formula
        this.values.set(key, val);
    }

    get(row, column) {
        const key = `${row},${column}`;
        if (this.formulas.has(key)) {
            let total = 0;
            for (const [ref, count] of this.formulas.get(key)) {
                const [r, c] = ref.split(',');
                total += count * this.get(Number(r), c);
            }
            return total;
        }
        return this.values.get(key) ?? 0;
    }

    sum(row, column, numbers) {
        const refs = new Map();
        for (const item of numbers) {
            const [start, end = start] = item.split(':');
            const r1 = Number(start.slice(1)), r2 = Number(end.slice(1));
            const c1 = start.charCodeAt(0), c2 = end.charCodeAt(0);
            for (let r = r1; r <= r2; r++) {
                for (let c = c1; c <= c2; c++) {
                    const ref = `${r},${String.fromCharCode(c)}`;
                    refs.set(ref, (refs.get(ref) ?? 0) + 1);
                }
            }
        }
        this.formulas.set(`${row},${column}`, refs);
        return this.get(row, column);
    }
}

Java Solution

Copy
class Excel {
    private final Map<String, Integer> values = new HashMap<>();
    private final Map<String, Map<String, Integer>> formulas = new HashMap<>();

    public Excel(int height, char width) {
    }

    public void set(int row, char column, int val) {
        String key = row + "," + column;
        formulas.remove(key); // A plain value replaces any formula
        values.put(key, val);
    }

    public int get(int row, char column) {
        String key = row + "," + column;
        Map<String, Integer> refs = formulas.get(key);
        if (refs == null) {
            return values.getOrDefault(key, 0);
        }
        int total = 0;
        for (Map.Entry<String, Integer> e : refs.entrySet()) {
            String[] parts = e.getKey().split(",");
            total += e.getValue() * get(Integer.parseInt(parts[0]), parts[1].charAt(0));
        }
        return total;
    }

    public int sum(int row, char column, String[] numbers) {
        Map<String, Integer> refs = new HashMap<>();
        for (String item : numbers) {
            String[] range = item.split(":");
            String start = range[0];
            String end = range.length > 1 ? range[1] : range[0];
            int r1 = Integer.parseInt(start.substring(1));
            int r2 = Integer.parseInt(end.substring(1));
            for (int r = r1; r <= r2; r++) {
                for (char c = start.charAt(0); c <= end.charAt(0); c++) {
                    refs.merge(r + "," + c, 1, Integer::sum);
                }
            }
        }
        formulas.put(row + "," + column, refs);
        return get(row, column);
    }
}