There is a strange printer with the following two special requirements:

On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.
Return true if it is possible to print the matrix targetGrid, otherwise, return false.
 
Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:
Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
Example 4:
Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

 
Constraints:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

Difficulty: interview

Starter code:

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

Solutions:
from collections import deque

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        grids = targetGrid
        num_to_range = dict()
        for i, row in enumerate(targetGrid):
            for j, val in enumerate(row):
                if val not in num_to_range:
                    # up, down, left, right
                    num_to_range[val] = [i, i, j, j]
                num_to_range[val][0] = min(num_to_range[val][0], i)
                num_to_range[val][1] = max(num_to_range[val][1], i)
                num_to_range[val][2] = min(num_to_range[val][2], j)
                num_to_range[val][3] = max(num_to_range[val][3], j)
        #print(num_to_range)
        
        m = len(grids)
        n = len(grids[0])
        grid_list = [[list() for j in range(n)] for i in range(m)]
        for num, val in list(num_to_range.items()):
            for i in range(val[0], val[1]+1):
                for j in range(val[2], val[3]+1):
                    grid_list[i][j].append(num)

        paths = {val: set() for val in list(num_to_range)}
        for i, row in enumerate(targetGrid):
            for j, val in enumerate(row):
                for parent in grid_list[i][j]:
                    if parent != val:
                        paths[parent].add(val)
                    
        parent_counter = {val: 0 for val in list(num_to_range)}
        for parent, childs in list(paths.items()):
            for child in childs:
                parent_counter[child] += 1
        
        queue = deque()
        for child, cnt in list(parent_counter.items()):
            if cnt == 0:
                queue.append(child)
        
        seen = set()
        while queue:
            parent = queue.popleft()
            seen.add(parent)
            for child in paths[parent]:
                parent_counter[child] -= 1
                if parent_counter[child] == 0:
                    queue.append(child)
                
        
        
        return len(seen) == len(num_to_range)
                


SIDE_LEFT = 'left'
SIDE_RIGHT = 'right'
SIDE_TOP = 'top'
SIDE_BOTTOM = 'bottom'

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        
        # Step 1: Get the set of the different colours being used
        colour_set = set()
        for row in targetGrid:
            for cell in row:
                colour_set.add(cell)
        
        # Step 2: Determine the size of each rectangle and the colours that overlap
        colour_overlap_info = self.get_colour_boundaries_and_overlap(targetGrid, colour_set)
        #print(colour_set, colour_overlap_info)

        # Step 3: Loop over the overlapping info. With each pass, print from the last colours downward. In this way, we'll determine
        # which colours we will print going backwards. If we can't print a colour underneath in an iteration, we've failed
        remaining_colours = colour_set.copy()
        untangled_colours = set()
        while remaining_colours:
            new_untangled_colours = set()
            for colour in remaining_colours:
                # Remove any colours that have been untangled
                colour_overlap_info[colour] -= untangled_colours
                if len(colour_overlap_info[colour]) == 0:
                    # We just untangled this one!
                    new_untangled_colours.add(colour)
            
            # Check if we've untangled anything new. If not, exit
            #print(new_untangled_colours)
            if new_untangled_colours:
                untangled_colours |= new_untangled_colours  # Add them to the full set
                remaining_colours -= new_untangled_colours  # Remove them from the full list
            else:
                break
        
        return len(remaining_colours) == 0  # If we've untangled everything, there are no remaining colours and it can be printed
                    
        
    def get_colour_boundaries_and_overlap(self, targetGrid, colour_set):
        # Determine the size of each rectangle and the colours that overlap
        colours_info = {}
        for colour in colour_set:
            
            # Get the boundaries
            boundaries = {}
            for row_index, row in enumerate(targetGrid):
                for col_index, cell in enumerate(row):
                    if cell == colour:
                        # Update the boundaries
                        if not boundaries:
                            # Initialize
                            boundaries = {
                                SIDE_LEFT: col_index,
                                SIDE_RIGHT: col_index,
                                SIDE_TOP: row_index,
                                SIDE_BOTTOM: row_index
                            }
                        else:
                            # Update the boundaries. Note that top can't move but left can
                            if boundaries[SIDE_LEFT] > col_index:
                                boundaries[SIDE_LEFT] = col_index
                            if boundaries[SIDE_RIGHT] < col_index:
                                boundaries[SIDE_RIGHT] = col_index
                            if boundaries[SIDE_BOTTOM] < row_index:
                                boundaries[SIDE_BOTTOM] = row_index
            #print(colour, boundaries)
            
            # Now that we have the boundaries, get the colours inside them
            overlapping_colours = set()
            for row_index in range(boundaries[SIDE_TOP], boundaries[SIDE_BOTTOM] + 1):
                for col_index in range(boundaries[SIDE_LEFT], boundaries[SIDE_RIGHT] + 1):
                    cell = targetGrid[row_index][col_index]
                    if cell != colour:
                        overlapping_colours.add(cell)
            
            # Save the data
            colours_info[colour] = overlapping_colours
        
        return colours_info
        


class Solution:
    from collections import defaultdict, Counter
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        shapes = {}  # color: [min_r, max_r, min_c, max_c]
        
        for i, row in enumerate(targetGrid):
            for j, color in enumerate(row):
                if color not in shapes:
                    shapes[color] = [i, i, j, j]
                else:
                    shapes[color][0] = min(shapes[color][0], i)
                    shapes[color][1] = max(shapes[color][1], i)
                    shapes[color][2] = min(shapes[color][2], j)
                    shapes[color][3] = max(shapes[color][3], j)
                    
        edges = defaultdict(set)
        
        for color, [min_r, max_r, min_c, max_c] in list(shapes.items()):
            for r in range(min_r, max_r + 1):
                for c in range(min_c, max_c + 1):
                    if targetGrid[r][c] != color:
                        edges[color].add(targetGrid[r][c])
                        
        deps = Counter()
        for _, ts in list(edges.items()):
            for c in ts:
                deps[c] += 1
                
        layer = [c for c in list(shapes.keys()) if not deps[c]]
        while layer:
            new_layer = []
            for c in layer:
                for t in edges[c]:
                    deps[t] -= 1
                    if not deps[t]:
                        new_layer.append(t)
            layer = new_layer
        
        return all(not v for c, v in list(deps.items()))
                


class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        a = [(math.inf, math.inf, -math.inf, -math.inf) for _ in range(61)]
        source = [[0] * len(targetGrid[0]) for _ in targetGrid]
        for i in range(len(targetGrid)):
            for j in range(len(targetGrid[i])):
                a[targetGrid[i][j]] = (min(a[targetGrid[i][j]][0], j), min(a[targetGrid[i][j]][1], i), max(a[targetGrid[i][j]][2], j), max(a[targetGrid[i][j]][3], i))
        gr = defaultdict(set)
        for p in range(len(a)):
            x, y, z, t = a[p]
            if x != math.inf:
                for i in range(y, t + 1):
                    for j in range(x, z + 1):
                        if targetGrid[i][j] != p:
                            gr[p].add(targetGrid[i][j])
        visited = set()
        inp = set()
        def dfs(k):
            inp.add(k)
            for x in gr[k]:
                if x in inp:
                    return False
                elif x not in visited and not dfs(x):
                    return False
            inp.remove(k)
            visited.add(k)
            return True
        for i in range(61):
            if i not in visited and not dfs(i):
                return False
        return True


class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        
        top = defaultdict(lambda: float('inf'))
        bottom = defaultdict(lambda: -1)
        
        left = defaultdict(lambda: float('inf'))
        right = defaultdict(lambda: -1)
        
        for row in range(len(targetGrid)):
            for col in range(len(targetGrid[row])):
                color = targetGrid[row][col]
                
                top[color] = min(top[color], row)
                bottom[color] = max(bottom[color], row)
                
                left[color] = min(left[color], col)
                right[color] = max(right[color], col)
                
        edges = defaultdict(list)
        
        for row in range(len(targetGrid)):
            for col in range(len(targetGrid[row])):
                color = targetGrid[row][col]
                
                for otherColor in top:
                    if color != otherColor and top[otherColor] <= row <= bottom[otherColor] and left[otherColor] <= col <= right[otherColor]:
                        edges[otherColor].append(color)
        
        # detect if there's a cycle in directed graph
        nodestates = [0 for _ in range(61)] # 0 not visited, 1 being visited, 2 done
        
        def dfs(current):
            nodestates[current] = 1
            
            for neighbor in edges[current]:
                if nodestates[neighbor] == 1:
                    # detect an edge
                    return True
                elif nodestates[neighbor] == 0:
                    dfs(neighbor)
            
            nodestates[current] = 2
        
        cycleDetected = False
        for node in top:
            if nodestates[node] == 0:
                if dfs(node):
                    cycleDetected = True
                    break
        
        return not cycleDetected
        
        
                        


class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        # FIND RECTANGLE BOUNDARIES FOR EACH COLOR
        boundaries = [(math.inf, math.inf, -math.inf, -math.inf) for _ in range(61)]
        for i in range(len(targetGrid)):
            for j in range(len(targetGrid[i])):
                color = targetGrid[i][j]
                min_i, min_j, max_i, max_j = boundaries[color]
                boundaries[color] = (min(min_i, i), min(min_j, j), max(max_i, i), max(max_j, j))

        # BUILD GRAPH
        graph = defaultdict(set)
        for color in range(len(boundaries)):
            min_i, min_j, max_i, max_j = boundaries[color]
            if min_i != math.inf:
                for i in range(min_i, max_i + 1):
                    for j in range(min_j, max_j + 1):
                        if targetGrid[i][j] != color:
                            graph[color].add(targetGrid[i][j])

        # DETECT CYCLES IN GRAPH
        visited = set()
        in_progress = set()
        def dfs(source):
            in_progress.add(source)
            for vertex in graph[source]:
                if (vertex in in_progress) or (vertex not in visited and not dfs(vertex)):
                    return False
            in_progress.remove(source)
            visited.add(source)
            return True

        for color in range(61):
            if color not in visited and not dfs(color):
                return False
        return True

# 1591. Strange Printer II

def walk (grid):
    for i, row in enumerate (grid):
        for j, elem in enumerate (row):
            yield ((i, j), elem)

def extend (bound, ij):
    i, j = ij
    if bound is None:
        return (ij, ij)
    else:
        ((i0, j0), (i1, j1)) = bound
        return (
            (min (i0, i), min (j0, j)),
            (max (i1, i), max (j1, j)),
        )

def contains (bound, ij):
    i, j = ij
    ((i0, j0), (i1, j1)) = bound
    return i0 <= i <= i1 and j0 <= j <= j1

def has_toposort (prereq):
    roots = [x for x in prereq if not prereq[x]]
    while roots:
        r = roots.pop ()
        del prereq[r]
        for c in prereq:
            if r in prereq[c]:
                prereq[c].remove (r)
                if not prereq[c]:
                    roots.append (c)
    return not prereq

def printable (grid):
    m, n = len (grid), len (grid[0])
    assert m >= 1 and n >= 1

    colors = {c for row in grid for c in row}
    bounds = {c: None for c in colors}

    for ((i, j), c) in walk (grid):
        bounds[c] = extend (bounds[c], (i, j))

    prereq = {c: set() for c in colors}
    for ((i, j), c) in walk (grid):
        for c2 in colors:
            if c2 == c: continue
            if contains (bounds[c2], (i, j)):
                prereq[c].add (c2)

    return has_toposort (prereq)

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

from collections import defaultdict
class Solution:
    def all_same(self, left, right, bottom, top, color):
        for i in range(bottom, top+1):
            for j in range(left, right+1):
                if self.grid[i][j] and self.grid[i][j] != color:
                    return False
        return True
    
    def fill(self, left, right, bottom, top):
        for i in range(bottom, top+1):
            for j in range(left, right+1):
                self.grid[i][j] = 0
                
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        self.rect = defaultdict(lambda : [10**9, -10**9, 10**9, -10**9])
        for i, row in enumerate(targetGrid):
            for j, color in enumerate(row):
                self.rect[color][0] = min(self.rect[color][0], j)
                self.rect[color][1] = max(self.rect[color][1], j)
                self.rect[color][2] = min(self.rect[color][2], i)
                self.rect[color][3] = max(self.rect[color][3], i)
        self.grid = targetGrid
        while self.rect:
            for color in self.rect:
                left, right, bottom, top = self.rect[color]
                if self.all_same(left, right, bottom, top, color):
                    self.fill(left, right, bottom, top)
                    self.rect.pop(color)
                    break
            else:         
                return False
        return True

class Solution:
    def isPrintable(self, A: List[List[int]]) -> bool:
        m, n = len(A), len(A[0])
        
        c = collections.Counter()
        dic = collections.defaultdict(lambda: [m+n, -1, m + n, -1, 0])
        seen = set()
        removed = set()
        for i, row in enumerate(A):
            for j, x in enumerate(row):
                dic[x][0] = min(dic[x][0], i)
                dic[x][2] = min(dic[x][2], j)
                dic[x][1] = max(dic[x][1], i)
                dic[x][3] = max(dic[x][3], j)
                dic[x][4] += 1
                seen.add(x)
        #print(dic)
        def helper(x):
            return abs((dic[x][1] - dic[x][0] + 1)*(dic[x][3] - dic[x][2] + 1) - dic[x][4])
        
        temp = sorted(seen, key = helper)
        
        #print(temp)
        
        k = 0
        #flag = True
        while len(temp) != len(removed):
            #flag= False 
            for t in temp:
                if t in removed: continue
                if helper(t) == 0:
                    removed.add(t)
                    break
                else:
                    a, b, c, d, total = dic[t]
                    flag = True
                    for i in  range(a, b + 1):
                        for j in range(c, d + 1):
                            if A[i][j]!= t and A[i][j] not in removed:
                                flag = False
                                break
                        if not flag:
                            break
                    #print(t, flag)
                    if flag:
                        removed.add(t)
                        break
            else:
                break
        return len(temp) == len(removed)
                        




class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        coverage = dict()
        for y in range(len(targetGrid)):
            for x in range(len(targetGrid[y])):
                val = targetGrid[y][x]
                if val not in coverage:
                    coverage[val] = (y,x,y,x)
                else:
                    asdf = coverage[val]
                    asdf = ( min(asdf[0],y), min(asdf[1],x), max(asdf[2],y), max(asdf[3],x) )
                    coverage[val] = asdf
        print(coverage)
        before = dict()
        done = set()
        for color in coverage:
            asdf = coverage[color]
            s = set()
            for y in range(asdf[0], asdf[2]+1):
                for x in range(asdf[1] ,asdf[3]+1):
                    s.add(targetGrid[y][x])
                if color in s:
                    s.remove(color)
            before[color] = s
        print(before)
        
        while len(before) > 0:
            gotOne = False
            for color in list(before.keys()):
                dependencies = before[color]
                dependencies = dependencies - done
                if len(dependencies) == 0:
                    before.pop(color)
                    done.add(color)
                    gotOne = True
                else:
                    before[color] = dependencies
            if gotOne == False:
                return False
        return True

import queue
class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        color_bounds = {}
        for i, row in enumerate(targetGrid):
            for j, color in enumerate(row):
                if not color in color_bounds:
                    color_bounds[color] = {'row': [1e6,-1e6], 'col': [1e6,-1e6]}
                color_bounds[color]['row'][0] = min(color_bounds[color]['row'][0], i)
                color_bounds[color]['row'][1] = max(color_bounds[color]['row'][1], i)
                color_bounds[color]['col'][0] = min(color_bounds[color]['col'][0], j)
                color_bounds[color]['col'][1] = max(color_bounds[color]['col'][1], j)
        graph = collections.defaultdict(list)
        degree = Counter()
        for color, bounds in list(color_bounds.items()):
            seen = set()
            for i in range(bounds['row'][0], bounds['row'][1] + 1):
                for j in range(bounds['col'][0], bounds['col'][1] + 1):
                    other_color = targetGrid[i][j]
                    if other_color != color and other_color not in seen:
                        seen.add(other_color)
                        graph[other_color].append(color)
                        degree[color] += 1
        q = queue.Queue()
        for color in list(color_bounds.keys()):
            if degree[color] == 0:
                q.put(color)
        processed_nodes = 0
        while not q.empty():
            color = q.get()
            processed_nodes += 1
            for next_color in graph[color]:
                degree[next_color] -= 1
                if degree[next_color] == 0:
                    q.put(next_color)
        return processed_nodes == len(color_bounds)
            


class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        R = len(targetGrid)
        C = len(targetGrid[0])
        WHITE = 0
        GRAY = 1
        BLACK = 2
        boxes = collections.defaultdict(lambda: [61, 61, -1, -1])
        
        for r, row in enumerate(targetGrid):
            for c, v in enumerate(row):
                boxes[v][0] = min(boxes[v][0], r)
                boxes[v][1] = min(boxes[v][1], c)
                boxes[v][2] = max(boxes[v][2], r)
                boxes[v][3] = max(boxes[v][3], c)
                
        graph = { color: set() for color in boxes }
        
        for color, (r1, c1, r2, c2) in boxes.items():
            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if targetGrid[r][c] != color:
                        graph[color].add(targetGrid[r][c])
                 
        state = collections.defaultdict(int)
        
        def dfs(u):
            state[u] = GRAY
            
            for v in graph[u]:
                if state[v] == WHITE:
                    if not dfs(v):
                        return False
                elif state[v] == GRAY:
                    return False
                
            state[u] = BLACK
            return True
        
        for s in graph:
            if state[s] == WHITE:
                if not dfs(s):
                    return False
                
        return True

class Solution:
    def isPrintable(self,M: List[List[int]]) -> bool:
        colorA =collections.defaultdict(lambda:[61,61,-1,-1]) # (top, left, bottom, right)
        for r, row in enumerate(M):
            for c, color in enumerate(row):
                colorA[color][0] = min(colorA[color][0], r)
                colorA[color][1] = min(colorA[color][1], c)
                colorA[color][2] = max(colorA[color][2], r)
                colorA[color][3] = max(colorA[color][3], c)
        graph={color:set() for color in colorA}
        for color,(top, left, bottom, right) in list(colorA.items()):
            for r in range(top, bottom + 1):
                for c in range(left, right+ 1):
                    if M[r][c] != color:
                        graph[color].add(M[r][c])
        W, G, B = 0, 1, 2
        state = collections.defaultdict(int)
        def check(node):
            state[node] = G
            for nei in graph[node]:
                if state[nei] == W:
                    if not check(nei):
                        return False
                if state[nei]== G:
                    return False
            state[node] = B
            return True
        for node in graph:
            if state[node] == W:
                if not check(node):
                    return False
        return True
                


class Solution:
    def isPrintable(self,M: List[List[int]]) -> bool:
        colorAreas=collections.defaultdict(lambda:[61,61,-1,-1]) #(top, left, bottom, right)
        for r, row in enumerate(M):
            for c, color in enumerate(row):
                colorAreas[color][0] = min(colorAreas[color][0] , r)
                colorAreas[color][1] = min(colorAreas[color][1] , c)
                colorAreas[color][2] = max(colorAreas[color][2] , r)
                colorAreas[color][3] = max(colorAreas[color][3] , c)
        graph = {color:set() for color in colorAreas}
        for color, (top, left, bottom, right) in list(colorAreas.items()):
            for r in range(top, bottom+1):
                for c in range(left, right+1):
                    if M[r][c] != color:
                        graph[color].add(M[r][c])
        W, G, B  =0, 1, 2
        state = collections.defaultdict(int)
        def check(node):
            state[node] = G
            for nei in graph[node]:
                if state[nei]==W:
                    if not check(nei):
                        return False
                if state[nei] == G:
                    return False
            state[node] = B
            return True
        for node in graph:
            if state[node] == W:
                if not check(node):
                    return False
        return True
        


class Grid(object):
    def __init__(self):
        self.ps = set()
        self.lx = 100
        self.ly = 100
        self.rx = 0
        self.ry = 0
    def add(self, x, y):
        self.ps.add((x, y))
        self.lx = min(self.lx, x)
        self.ly = min(self.ly, y)
        
        self.rx = max(self.rx, x)
        self.ry = max(self.ry, y)
    
    def is_full(self):
        return len(self.ps) == (self.rx-self.lx+1)*(self.ry-self.ly+1)
    
    def overlap(self, grid):
        # self on the left grid
        flag = self.rx < grid.lx
        # self on the upper grid
        flag = flag and self.ry > grid.ly
        # self on the right grid
        flag = flag and self.lx > grid.rx
        # self on the bottom grid
        flag = flag and self.ly < grid.ry
        return not flag
    
    def contain(self, grid):
        if not self.overlap(grid): return False
        for (x, y) in grid.ps:
            if self.lx <= x <= self.rx and self.ly <= y <= self.ry: return True
        return False
    
        
    def __str__(self):
        return '({0.lx}, {0.ly}), ({0.rx}, {0.ry})'.format(self)
    
class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        grids = defaultdict(Grid)
        for x, row in enumerate(targetGrid):
            for y, c in enumerate(row):
                grids[c].add(x, y)
                
        colors = grids.keys()

        graph, degree = defaultdict(set), defaultdict(int)
        vis = set()
        for c1 in colors:
            for c2 in colors:
                if c1 == c2 or (c1, c2) in vis: continue
                vis.add((c1, c2))
                if grids[c1].contain(grids[c2]):
                    graph[c1].add(c2)
                    degree[c2] += 1
              
       
        # for c in colors:
#             print(c, grids[c])         
#         print(graph)
#         print(degree)
        
        q = []
        for c in colors: 
            if degree[c] == 0: 
                q.append(c)
        
        vis = []
        while q:
            c1 = q.pop()
            vis.append(c1)
            for c2 in graph[c1]:
                degree[c2] -= 1
                if degree[c2] == 0: q.append(c2)
        
        # print(vis)
        return len(vis) == len(colors)

class Solution:
    def isPrintable(self, target: List[List[int]]) -> bool:
        TOP, LEFT, BOTTOM, RIGHT = 0, 1, 2, 3
        M, N = len(target), len(target[0])
        boxes = defaultdict(lambda: [math.inf, math.inf, -math.inf, -math.inf])
        for i, row in enumerate(target):
            for j, x in enumerate(row):
                boxes[x][TOP] = min(boxes[x][TOP], i)
                boxes[x][LEFT] = min(boxes[x][LEFT], j)
                boxes[x][BOTTOM] = max(boxes[x][BOTTOM], i)
                boxes[x][RIGHT] = max(boxes[x][RIGHT], j)
        graph = {color: set() for color in boxes}
        for color, (i1, j1, i2, j2) in boxes.items():
            for i in range(i1, i2 + 1):
                for j in range(j1, j2 + 1):
                    if target[i][j] != color:
                        graph[color].add(target[i][j])
        WHITE, GRAY, BLACK = 0, 1, 2
        color = defaultdict(int)

        def dfs(u):
            color[u] = GRAY
            for v in graph[u]:
                if color[v] == GRAY:
                    return False
                elif color[v] == WHITE and not dfs(v):
                    return False
            color[u] = BLACK
            return True

        return all(color[u] == BLACK or dfs(u) for u in graph)

class Component:
    def __init__(self, color):
        self.cells = set()
        self.color = color
        self.min_row = float('inf')
        self.max_row = float('-inf')
        self.min_col = float('inf')
        self.max_col = float('-inf')
        
    def add_cell(self, u):
        self.cells.add(u)
        self.min_row = min(self.min_row, u[0])
        self.max_row = max(self.max_row, u[0])
        self.min_col = min(self.min_col, u[1])
        self.max_col = max(self.max_col, u[1])

    def remove_cell(self, u):
        self.cells.remove(u)

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        grid = targetGrid
        
        def discover_components():
            components = {}
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    color = grid[i][j]
                    if color not in components:
                        components[color] = Component(color)
                    components[color].add_cell((i, j))
            return components
        
        def is_rectangular(c):
            for i in range(c.min_row, c.max_row + 1):
                for j in range(c.min_col, c.max_col + 1):
                    if grid[i][j] != c.color:
                        return False
            return True
        
        def replace_holes(cx, marked_for_removal):
            # Go through cells from components marked for removal and see if the
            # holes in cx could be replaced with the cells that we will remove
            for i in range(cx.min_row, cx.max_row + 1):
                hole_colors = set()
                for j in range(cx.min_col, cx.max_col + 1):
                    if grid[i][j] == cx.color:
                        continue
                    if grid[i][j] not in marked_for_removal:
                        return

            for i in range(cx.min_row, cx.max_row + 1):
                for j in range(cx.min_col, cx.max_col + 1):
                    if grid[i][j] != cx.color:
                        cx.add_cell((i, j))
                        hc = grid[i][j]
                        marked_for_removal[hc].remove_cell((i, j))
                        if len(marked_for_removal[hc].cells) == 0:
                            del(marked_for_removal[hc])
                        grid[i][j] = cx.color

        components = discover_components()
        marked_for_removal = {}
        while len(components) > 0:
            found_new_comp_to_remove = False
            for c in components:
                if is_rectangular(components[c]):
                    marked_for_removal[c] = components[c]
                    del(components[c])
                    found_new_comp_to_remove = True
                    break
            if not found_new_comp_to_remove:
                return False
            
            for c in list(components.keys()):
                replace_holes(components[c], marked_for_removal)

        return True


class Component:
    def __init__(self, color):
        self.cells = set()
        self.color = color
        self.min_row = float('inf')
        self.max_row = float('-inf')
        self.min_col = float('inf')
        self.max_col = float('-inf')
        
    def add_cell(self, u):
        self.cells.add(u)
        self.min_row = min(self.min_row, u[0])
        self.max_row = max(self.max_row, u[0])
        self.min_col = min(self.min_col, u[1])
        self.max_col = max(self.max_col, u[1])

    def remove_cell(self, u):
        self.cells.remove(u)

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        grid = targetGrid
        
        def discover_components():
            components = {}
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    color = grid[i][j]
                    if color not in components:
                        components[color] = Component(color)
                    components[color].add_cell((i, j))
            return components
        
        def is_complete_rect(c):
            for i in range(c.min_row, c.max_row + 1):
                for j in range(c.min_col, c.max_col + 1):
                    if grid[i][j] != c.color:
                        return False
            return True
        
        def replace_holes(cx, marked_for_removal):
            # Go through cells from components marked for removal and see if the
            # holes in cx could be replaced with the cells that we will remove
            for i in range(cx.min_row, cx.max_row + 1):
                hole_colors = set()
                for j in range(cx.min_col, cx.max_col + 1):
                    if grid[i][j] == cx.color:
                        continue
                    if grid[i][j] not in marked_for_removal:
                        return

            for i in range(cx.min_row, cx.max_row + 1):
                for j in range(cx.min_col, cx.max_col + 1):
                    if grid[i][j] != cx.color:
                        cx.add_cell((i, j))
                        hc = grid[i][j]
                        marked_for_removal[hc].remove_cell((i, j))
                        if len(marked_for_removal[hc].cells) == 0:
                            del(marked_for_removal[hc])
                        grid[i][j] = cx.color

        components = discover_components()
        marked_for_removal = {}
        while len(components) > 0:
            found_new_comp_to_remove = False
            for c in components:
                if is_complete_rect(components[c]):
                    marked_for_removal[c] = components[c]
                    del(components[c])
                    found_new_comp_to_remove = True
                    break
            if not found_new_comp_to_remove:
                return False
            
            for c in list(components.keys()):
                replace_holes(components[c], marked_for_removal)

        return True


class Component:
    def __init__(self, color):
        self.cells = set()
        self.color = color
        self.min_row = float('inf')
        self.max_row = float('-inf')
        self.min_col = float('inf')
        self.max_col = float('-inf')
        
    def add_cell(self, u):
        self.cells.add(u)
        self.min_row = min(self.min_row, u[0])
        self.max_row = max(self.max_row, u[0])
        self.min_col = min(self.min_col, u[1])
        self.max_col = max(self.max_col, u[1])

    def remove_cell(self, u):
        self.cells.remove(u)

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        grid = targetGrid
        
        def discover_components():
            components = {}
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    color = grid[i][j]
                    if color not in components:
                        components[color] = Component(color)
                    components[color].add_cell((i, j))
            return components
        
        def is_complete_rect(c):
            for i in range(c.min_row, c.max_row + 1):
                for j in range(c.min_col, c.max_col + 1):
                    if grid[i][j] != c.color:
                        return False
            return True
        
        def replace_holes(cx, marked_for_removal):
            # Go through cells from components marked for removal and see if the
            # holes in cx could be replaced with the cells that we will remove
            for i in range(cx.min_row, cx.max_row + 1):
                hole_colors = set()
                for j in range(cx.min_col, cx.max_col + 1):
                    if grid[i][j] == cx.color:
                        continue
                    if grid[i][j] not in marked_for_removal:
                        return

            for i in range(cx.min_row, cx.max_row + 1):
                for j in range(cx.min_col, cx.max_col + 1):
                    if grid[i][j] != cx.color:
                        cx.add_cell((i, j))
                        hc = grid[i][j]
                        marked_for_removal[hc].remove_cell((i, j))
                        if len(marked_for_removal[hc].cells) == 0:
                            del(marked_for_removal[hc])
                        grid[i][j] = cx.color

        components = discover_components()
        marked_for_removal = {}
        while len(components) > 0:
            found_rect_to_remove = False
            for c in components:
                if is_complete_rect(components[c]):
                    marked_for_removal[c] = components[c]
                    del(components[c])
                    found_rect_to_remove = True
                    break
            if not found_rect_to_remove:
                return False
            
            for c in list(components.keys()):
                replace_holes(components[c], marked_for_removal)

        return True