Problem statement

https://leetcode.com/problems/design-excel-sum-formula/

Solution

The idea is that our Excel table actually is DAG, that is graph without cycles.

  1. We initialize our matrix as 2D array of dictionaries: for each cell we have value val and edges E: our connections with other cells with weights (we need weights, because we can have something like A3 = 2A2 + 3B1). Time complexity is O(WH).
  2. set(r, c, v) function just put value v to corresponding cell and make connections empty, it is important: “this sum formula should exist until this cell is overlapped by another value or another sum formula”. Time complexity is O(1).
  3. get(r, c). Here we need to check if corresponding edges E for this cell is empty. If it is, it means that we reached leaf in our tree and we just return value. If edges are not empty, we need to recursively call our get function for all children and sum it. Time complexity is potentially O(W^2H^2), because we can have fully one-directional connected graph. More precisely, it is O(WHE), where E is current number of edges in our graph.
  4. sum(r, c, strs) function: here we need to construct connections in our graph: first, we need to process each element in strs and create defaultdict m: what cells we need to take with which weights. Complexity is O(WHE) < O(W^2H^2), where E again is number of edges in our graph.

Complexity

Space complexity is O(WHE) < O(W^2H^2), time complexities explained previously.

Code

class Excel:
    def __init__(self, H, W):
        self.matrix=[[{"val":0, "E": None} for _ in range(ord(W) - 64)] for _ in range(H)]

    def set(self, r, c, v):
        self.matrix[r-1][ord(c) - 65] = {"val":v, "E":None}

    def get(self, r, c):
        cell = self.matrix[r - 1][ord(c) - 65]
        if not cell["E"]: return cell["val"]
        return sum([cell["E"][k]*self.get(k[0] + 1, chr(k[1] + 65)) for k in cell["E"]])

    def sum(self, r, c, strs):
        m = defaultdict(int)
        for s in strs:
            l = s.split(':')
            i1, j1 = int(l[0][1:]) - 1, ord(l[0][0]) - 65
            i2 = i1 if len(l) == 1 else int(l[1][1:]) - 1
            j2 = j1 if len(l) == 1 else ord(l[1][0]) - 65
            for i in range(i1, i2+1):
                for j in range(j1, j2+1):
                    m[i, j] += 1
        self.matrix[r - 1][ord(c) - 65] = {"val":0, "E":m}
        return self.get(r, c)