1
# Runtime: 514 ms (Top 80.64%) | Memory: 14.5 MB (Top 44.35%)
2
from graphlib import TopologicalSorter, CycleError
3

4
Color = int
5
Corner = Tuple[int, int]
6
Rect = Tuple[Corner, Corner]  # [upper-left, lower-right (non-inclusive)]
7
Layer = Tuple[Color, Rect]
8

9

10
class Solution:
11
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
12
        # Runtime is the summation of several steps but is dominated by the second step
13
        # O(M*N + C*C*M*N + (O(C*C) + O(M*N)) + M*N) -> O(C*C*M*N)
14
        def compare(a: Layer, b: Layer) -> int:
15
            """
16
            Determine if two rectangles overlap.
17

18
            Return:
19
                -1 if b is over a
20
                0 if there is no overlap or an order cannot be determined (the overlap contains no elements of a or b)
21
                1 if a is over b
22
            """
23
            val_a, (a_ul, a_lr) = a
24
            val_b, (b_ul, b_lr) = b
25

26
            # Get overlap rectangle
27
            ul, lr = (
28
                (max(a_ul[0], b_ul[0]), max(a_ul[1], b_ul[1])),
29
                (min(a_lr[0], b_lr[0]), min(a_lr[1], b_lr[1])),
30
            )
31

32
            # If either dimension is non-positive, there is no overlap
33
            if lr[0] - ul[0] <= 0 or lr[1] - ul[1] <= 0:
34
                return 0
35

36
            # Find the first element matching a or b in the overlap rectangle.
37
            # We'll consider that the "over" value.
38
            for r in range(ul[0], lr[0]):
39
                for c in range(ul[1], lr[1]):
40
                    if targetGrid[r][c] == val_b:
41
                        return -1
42
                    elif targetGrid[r][c] == val_a:
43
                        return 1
44
            # We could find no values from a or b in the overlap.
45
            # The result is indeterminate.
46
            return 0
47

48
        # Generate the enclosing rectangles for each visible color (ie. layers).
49
        # O(M*N)
50
        rects: Dict[Color, Rect] = defaultdict(lambda: ([100, 100], [0, 0]))
51
        for r, row in enumerate(targetGrid):
52
            for c, val in enumerate(row):
53
                ul, lr = rects[val]
54
                rects[val] = (
55
                    (min(ul[0], r), min(ul[1], c)),
56
                    (max(lr[0], r + 1), max(lr[1], c + 1)),
57
                )
58

59
        # Compare every pair of layers.
60
        # If overlap is detected, record that the "upper" rectangle depends on the "lower" one.
61
        # O(C*C*M*N) # Number of colors
62
        layers: List[Layer] = list(rects.items())
63
        graph: Dict[Layer, Set[Layer]] = {layer: set() for layer in layers}
64
        for i, a in enumerate(layers):
65
            for b in layers[i + 1 :]:
66
                if (cmp := compare(a, b)) < 0:
67
                    graph[b].add(a)
68
                elif cmp > 0:
69
                    graph[a].add(b)
70

71
        # Use topological sort on the graph to reproduce the printing order (in the absence
72
        # of cycles) and print our own grid.
73
        # O(C*C) + O(M*N) // O(C*C) is derived from topological sort O(V+E)
74
        try:
75
            grid = [[0] * len(targetGrid[0]) for _ in targetGrid]
76
            for color, (ul, lr) in TopologicalSorter(graph).static_order():
77
                for r in range(ul[0], lr[0]):
78
                    for c in range(ul[1], lr[1]):
79
                        grid[r][c] = color
80
        except CycleError:
81
            return False
82

83
        # Compare the grids
84
        # O(M*N)
85
        return grid == targetGrid