Skip to content

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})$
 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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]};
  }
};
 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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]);
  }
}
 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
class Cell:
  def __init__(self, val: int, posCount: Optional[Dict[Tuple[int, int], int]]):
    self.val = val
    self.posCount = posCount  # {pos, count}


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

  def set(self, row: int, column: str, val: int) -> None:
    self.sheet[row - 1][ord(column) - ord('A')] = Cell(val, None)

  def get(self, row: int, column: str) -> int:
    cell = self.sheet[row - 1][ord(column) - ord('A')]
    if cell.posCount:
      return sum(self.get(*pos) * freq for pos, freq in cell.posCount.items())
    return cell.val

  def sum(self, row: int, column: str, numbers: List[str]) -> int:
    self.sheet[row - 1][ord(column) - ord('A')].posCount = self._parse(numbers)
    return self.get(row, column)

  def _parse(self, numbers: List[str]):
    count = Counter()
    for n in numbers:
      s, e = n.split(':')[0], n.split(':')[1] if ':' in n else n
      for i in range(int(s[1:]), int(e[1:]) + 1):
        for j in range(ord(s[0]) - ord('A'), ord(e[0]) - ord('A') + 1):
          count[(i, chr(j + ord('A')))] += 1
    return count