Problem statement

https://leetcode.com/problems/strange-printer-ii/

Solution

One idea is to start for the end: we denote by 0 symbols which can be any color and each time we look for rectangle which consists fully of one color: that means it can have [0, col] colors. Rectangle defined by smallest and biggest of each coordinates. On each iteration we look for rectangle to paint in 0 and if we can and we still have elements to paint, return False. If all array have only zeroes, return True.

Complexity

Complexity of this approach is O(m*n*C^2), where C is number of colors.

Code

class Solution:
    def isPrintable(self, G):
        m, n = len(G), len(G[0])
        while True:
            dx = defaultdict(list)
            dy = defaultdict(list)
            for x, y in product(range(n), range(m)):
                dx[G[y][x]].append(x)
                dy[G[y][x]].append(y)
          
            changed = False
            
            for col in dx:
                if len(dx[col]) == 0 or col == 0: continue
                x1, x2 = min(dx[col]), max(dx[col])
                y1, y2 = min(dy[col]), max(dy[col])
                
                R = list(product(range(x1, x2+1), range(y1, y2+1)))
                if all(G[y][x] in [0, col] for x, y in R):
                    for a, b in R: G[b][a] = 0
                    changed = True
                    break
                    
            if not changed and len(dx) != 1: return False
            if len(dx) == 1: return True

Remark

Actually, it can be solved faster if we use the idea of Topological sort: for each color define the minimum rectangle it can be covered with and then create graph of dependencies. Graph can be created either in O(m*n*C) if we iterate all colors and check if we have other colors inside. So, it is possible to solve problem in O(mnC). See similar problem 0936. Stamping The Sequence