leetcode/1591.py at main · lukeviens/leetcode · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
from typing import List

class Solution:
    def isPrintable(self, grid: List[List[int]]) -> bool:

        # look for top left and bottom right corners of rectangles
        # find outmost top, left, bottom, and right for each number
        def build(rects):
            for i in range(m):
                for j in range(n):
                    num = grid[i][j]
                    rect = rects.setdefault(num, [i, j, i, j])

                    if i < rect[0]:
                        rect[0] = i  # top
                    if j < rect[1]:
                        rect[1] = j  # left

                    if i > rect[2]:
                        rect[2] = i  # bottom
                    if j > rect[3]:
                        rect[3] = j  # right

            # sort by smallest rectangle
            rects = sorted(
                rects.items(),
                key=lambda r: (
                    (r[1][2] - r[1][0] + 1) *
                    (r[1][3] - r[1][1] + 1)
                )
            )


        # check if a rectangle is blocked
        def blocked(num):
            if num not in blockers:
                return False, None

            if blockers[num][0] in rects:
                return True, None

            idx = blockers[num][1]
            del blockers[num]

            return False, idx

        # for each top left, see if we can reach bottom right
        def check_nums():
            for num in rects.keys():
                is_blocked, index = blocked(num)
                if is_blocked:
                    continue

                top, left, bottom, right = rects[num]
                t, l, b, r = top, left, bottom, right

                if index:
                    t, l = index

                # see if it's a full rectangle
                is_rectangle = True
                while t != b or l != r:
                    if grid[t][l] != num and grid[t][l] not in used:
                        blockers[num] = [grid[t][l], [t, l]]
                        is_rectangle = False
                        break

                    l += 1
                    if l == r + 1 and t < b:
                        t, l = t + 1, left


                # if it's a full rectangle, delete it
                if is_rectangle is True:
                    return True, num

            return False, None


        # TOP LEFT BOTTOM RIGHT

        # find full rectangles and attempt to go backwards
        m = len(grid)
        n = len(grid[0])

        used = set()
        rects = {}  # rects[num] = [top, left, bottom, right]
        blockers = {}  # blockers[num] = num

        build(rects)

        while rects:
            found, num = check_nums()

            if found is False:
                return False

            rects.pop(num)
            used.add(num)

            if not rects:
                return True

        return True


s = Solution()

c1 = [[1,1,1,1],
      [1,2,2,1],
      [1,2,2,1],
      [1,1,1,1]]

c2 = [[1,1,1,1],
      [1,1,3,3],
      [1,1,3,4],
      [5,5,1,4]]

c3 = [[1,2,1],
      [2,1,2],
      [1,2,1]]

print(s.isPrintable(c1))
print(s.isPrintable(c2))
print(s.isPrintable(c3))