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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Graph algorithms

Data structures

Directed graphs

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:
					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)
		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:
		colour_set = set()
		for row in targetGrid:
			for cell in row:
				colour_set.add(cell)
		colour_overlap_info = self.get_colour_boundaries_and_overlap(targetGrid, colour_set)
		remaining_colours = colour_set.copy()
		untangled_colours = set()
		while remaining_colours:
			new_untangled_colours = set()
			for colour in remaining_colours:
				colour_overlap_info[colour] -= untangled_colours
				if len(colour_overlap_info[colour]) == 0:
					new_untangled_colours.add(colour)
			if new_untangled_colours:
				untangled_colours |= new_untangled_colours
				remaining_colours -= new_untangled_colours
			else:
				break
		return len(remaining_colours) == 0

	def get_colour_boundaries_and_overlap(self, targetGrid, colour_set):
		colours_info = {}
		for colour in colour_set:
			boundaries = {}
			for (row_index, row) in enumerate(targetGrid):
				for (col_index, cell) in enumerate(row):
					if cell == colour:
						if not boundaries:
							boundaries = {SIDE_LEFT: col_index, SIDE_RIGHT: col_index, SIDE_TOP: row_index, SIDE_BOTTOM: row_index}
						else:
							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
			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)
			colours_info[colour] = overlapping_colours
		return colours_info


class Solution:
	from collections import defaultdict, Counter

	def isPrintable(self, targetGrid: List[List[int]]) -> bool:
		shapes = {}
		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)
		nodestates = [0 for _ in range(61)]

		def dfs(current):
			nodestates[current] = 1
			for neighbor in edges[current]:
				if nodestates[neighbor] == 1:
					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:
		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))
		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])
		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


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)

		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)
		k = 0
		while len(temp) != len(removed):
			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
					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': [1000000.0, -1000000.0], 'col': [1000000.0, -1000000.0]}
				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])
		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 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):
		flag = self.rx < grid.lx
		flag = flag and self.ry > grid.ly
		flag = flag and self.lx > grid.rx
		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
		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)
		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):
			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