LeetCode Solutions Blog

Strange Printer II

Number: 1696

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an m x n matrix targetGrid where targetGrid[row][col] represents a color at position (row, col), determine if it is possible to print the grid using a strange printer. The printer can only print a solid rectangular pattern of a single color in one turn and each color may be used only once. When printing a rectangle, it covers any colors underneath. Return true if you can achieve targetGrid with a sequence of printing operations; otherwise, return false.

Key Insights

For each color present, determine its bounding rectangle (smallest rectangle that covers all occurrences).
Within that bounding rectangle, any cell that does not match the current color is evidence that another color was printed after the current one. This sets up a dependency relation.
Build a dependency graph where an edge from color A to color B indicates that A must be printed before B.
The problem reduces to checking if the dependency graph has a valid topological ordering (i.e. no cycles).

Space and Time Complexity

Time Complexity: O(m * n + k * m * n) where k is the number of distinct colors (k ≤ 60), so essentially O(m * n) Space Complexity: O(k + m * n) for storing the graph and the bounding boxes.

Solution

We start by scanning the targetGrid to determine, for each color, its minimum and maximum row and column indices (its bounding rectangle). Then, for each color, we examine every cell in its bounding rectangle. If a cell contains a different color D, then that means color D was painted over color C and should appear later. Therefore, we add an edge from C to D in our dependency graph. Once the graph is built, we perform a topological sort. If we can obtain a complete ordering without detecting a cycle, then the sequence of printer operations exists to form the targetGrid; otherwise, it is impossible.

Code Solutions

# Python solution for Strange Printer II
from collections import defaultdict, deque

def isPrintable(targetGrid):
    m, n = len(targetGrid), len(targetGrid[0])
    # initialize bounding boxes for each color. Format: color -> [min_row, max_row, min_col, max_col]
    bounds = {}
    
    # determine bounding rectangle for each color seen in grid
    for i in range(m):
        for j in range(n):
            color = targetGrid[i][j]
            if color not in bounds:
                bounds[color] = [i, i, j, j]
            else:
                bounds[color][0] = min(bounds[color][0], i)
                bounds[color][1] = max(bounds[color][1], i)
                bounds[color][2] = min(bounds[color][2], j)
                bounds[color][3] = max(bounds[color][3], j)
    
    # Build dependency graph: key -> set of colors that must be printed after key.
    graph = defaultdict(set)
    in_degree = {c: 0 for c in bounds}
    
    # For each color, check its bounding rectangle and add dependencies.
    for c, (min_row, max_row, min_col, max_col) in bounds.items():
        for i in range(min_row, max_row+1):
            for j in range(min_col, max_col+1):
                currentColor = targetGrid[i][j]
                if currentColor != c:
                    # If edge not already present, add edge from c -> currentColor.
                    if currentColor not in graph[c]:
                        graph[c].add(currentColor)
                        in_degree[currentColor] += 1
    
    # Topological sort: start from colors with 0 in-degree.
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    count = 0

    while queue:
        color = queue.popleft()
        count += 1
        for nextColor in graph[color]:
            in_degree[nextColor] -= 1
            if in_degree[nextColor] == 0:
                queue.append(nextColor)
    
    # If count equals the number of unique colors, a valid ordering exists.
    return count == len(in_degree)

# Example usage:
print(isPrintable([[1,1,1,1],
                   [1,2,2,1],
                   [1,2,2,1],
                   [1,1,1,1]]))  # Expected output: True