631. Design Excel Sum Formula

• Time:
  • Constructor: $O(\texttt{height} \cdot \texttt{width})$
  • set(row: int, column: chr, val: int)
  • get(row: int, column: chr): $O(1)$
  • sum(row: int, column: chr, numbers: list[str]): $O(|\texttt{numbers}|)$
• Space: $O(\texttt{height} \cdot \texttt{width})$

C++JavaPython

struct Cell {
  int val = 0;
  unordered_map<int, int> posCount;  // {pos: count}
};

class Excel {
 public:
  Excel(int height, char width)
      : width(width), sheet(height, vector<Cell>(width)) {}

  void set(int row, char column, int val) {
    getCell(row, column) = {val, {}};
  }

  int get(int row, char column) {
    const Cell& cell = getCell(row, column);
    if (cell.posCount.empty())
      return cell.val;

    int val = 0;
    for (const auto& [pos, count] : cell.posCount)
      val += get(pos / width + 1, pos % width + 'A') * count;
    return val;
  }

  int sum(int row, char column, vector<string> numbers) {
    getCell(row, column).posCount = parse(numbers);
    return get(row, column);
  }

 private:
  int width;
  vector<vector<Cell>> sheet;

  Cell& getCell(int row, char column) {
    return sheet[row - 1][column - 'A'];
  }

  unordered_map<int, int> parse(const vector<string>& numbers) {
    unordered_map<int, int> count;
    for (const string& s : numbers) {
      const auto [startRow, startCol, endRow, endCol] = parse(s);
      for (int i = startRow - 1; i < endRow; ++i)
        for (int j = startCol - 'A'; j < endCol - 'A' + 1; ++j)
          ++count[i * width + j];
    }
    return count;
  }

  tuple<int, char, int, char> parse(const string& s) {
    if (s.find(':') == string::npos)
      return {stoi(s.substr(1)), s[0], stoi(s.substr(1)), s[0]};

    const int colonIndex = s.find_first_of(':');
    const string& l = s.substr(0, colonIndex);
    const string& r = s.substr(colonIndex + 1);
    return {stoi(l.substr(1)), l[0], stoi(r.substr(1)), r[0]};
  }
};

class Cell {
  public int val = 0;
  public Map<Integer, Integer> posCount = new HashMap<>(); // {pos, count}
  public Cell(int val, Map<Integer, Integer> posCount) {
    this.val = val;
    this.posCount = posCount;
  }
}

class Excel {
  public Excel(int height, char width) {
    this.width = width;
    this.sheet = new Cell[height][width];

    for (int i = 0; i < height; ++i)
      for (int j = 0; j < width; ++j)
        sheet[i][j] = new Cell(0, null);
  }

  public void set(int row, char column, int val) {
    sheet[row - 1][column - 'A'] = new Cell(val, null);
  }

  public int get(int row, char column) {
    Cell cell = sheet[row - 1][column - 'A'];
    if (cell.posCount == null)
      return cell.val;

    int val = 0;
    for (Map.Entry<Integer, Integer> entry : cell.posCount.entrySet()) {
      final int pos = entry.getKey();
      final int count = entry.getValue();
      val += get(pos / width + 1, (char) ((pos % width) + 'A')) * count;
    }
    return val;
  }

  public int sum(int row, char column, String[] numbers) {
    sheet[row - 1][column - 'A'].posCount = parse(numbers);
    return get(row, column);
  }

  private int width;
  private Cell[][] sheet;

  private Map<Integer, Integer> parse(String[] numbers) {
    Map<Integer, Integer> count = new HashMap<>();

    for (final String s : numbers) {
      Pair<String, String> tokens = parse(s);
      final int startRow = Integer.parseInt(tokens.getKey().substring(1));
      final char startCol = tokens.getKey().charAt(0);
      final int endRow = Integer.parseInt(tokens.getValue().substring(1));
      final char endCol = tokens.getValue().charAt(0);
      for (int i = startRow - 1; i < endRow; ++i)
        for (int j = startCol - 'A'; j < endCol - 'A' + 1; ++j)
          count.merge(i * width + j, 1, Integer::sum);
    }

    return count;
  }

  private Pair<String, String> parse(final String s) {
    if (!s.contains(":"))
      return new Pair<>(s, s);

    String[] tokens = s.split(":");
    return new Pair<>(tokens[0], tokens[1]);
  }
}

from dataclasses import dataclass


@dataclass
class Cell:
  val: int = 0
  posCount: dict[tuple[int, int], int] | None = None


class Excel:
  def __init__(self, height: int, width: str):
    self.width = ord(width) - ord('A') + 1
    self.sheet = [[Cell() for _ in range(self.width)] for _ in range(height)]

  def set(self, row: int, column: str, val: int) -> None:
    self._getCell(row, column).val = val
    self._getCell(row, column).posCount = {}

  def get(self, row: int, column: str) -> int:
    cell = self._getCell(row, column)
    if not cell.posCount:
      return cell.val
    val = 0
    for pos, count in cell.posCount.items():
      val += self.get(pos // self.width + 1, chr(pos %
                      self.width + ord('A'))) * count
    return val

  def sum(self, row: int, column: str, numbers: list[str]) -> int:
    self._getCell(row, column).posCount = self._parse(numbers)
    return self.get(row, column)

  def _getCell(self, row: int, column: str) -> Cell:
    return self.sheet[row - 1][ord(column) - ord('A')]

  def _parse(self, numbers: list[str]) -> dict[int, int]:
    count: dict[int, int] = {}
    for s in numbers:
      startRow, startCol, endRow, endCol = self._parseRange(s)
      for i in range(startRow - 1, endRow):
        for j in range(ord(startCol) - ord('A'), ord(endCol) - ord('A') + 1):
          pos = i * self.width + j
          count[pos] = count.get(pos, 0) + 1
    return count

  def _parseRange(self, s: str) -> tuple[int, str, int, str]:
    if ':' not in s:
      return int(s[1:]), s[0], int(s[1:]), s[0]
    l, r = s.split(':')
    return int(l[1:]), l[0], int(r[1:]), r[0]