Strange Printer II: Topological Sort on Color Dependencies
You are given a grid of colors produced by a strange printer. The printer can only print solid, axis-aligned rectangles of a single color, and each new print completely covers whatever was underneath. Given the final result, can you determine whether any sequence of prints could have produced it? That is LeetCode 1591: Strange Printer II.
The problem
The printer works like this. In each turn, it picks a color and fills an axis-aligned rectangle with that color. The rectangle covers everything previously printed in that region. After some sequence of prints, the grid reaches its final state. You are given that final state and need to decide: is it actually achievable?
Think of it like painting on a canvas. You can paint rectangles one at a time, and each new rectangle hides whatever was underneath. The question is whether the final image could have been created by layering rectangles in some order.
Final grid
Each letter represents a color printed by the printer.
Bounding rectangles per color
Dashed outlines show each color's bounding rectangle. G and B are inside R's box, so R must print first.
The brute force approach
You could try every possible permutation of colors and simulate the printing process for each one, checking if the result matches the target grid. With up to 60 distinct colors, that is 60! orderings to check, which is astronomically large. Even pruning early does not make this feasible.
A slightly better brute force would be to use backtracking: pick a color to print first, simulate it, check if the remaining grid is still consistent, and recurse. But this still has exponential worst-case time and is far too slow for the given constraints.
The key insight
Instead of simulating the printing process, think about it as a dependency problem. For each color, compute its bounding rectangle (the smallest rectangle that contains all cells of that color in the final grid). If another color appears inside that bounding rectangle, it means the other color was printed after the current one, covering part of it.
This gives you a directed graph. An edge from color A to color B means "A must be printed before B." The grid is achievable if and only if this dependency graph has no cycle. If there is a cycle, the colors depend on each other in a circular way, and no valid print order exists.
This is the same core idea behind Course Schedule and other topological sort problems. Whenever you see "is there a valid ordering given these constraints," think dependency graph and cycle detection.
Step-by-step walkthrough
Step 1: Compute bounding boxes for each color.
Color R spans the full grid (rows 0-3, cols 0-3). G spans rows 1-2, cols 1-2. B spans rows 2-3, cols 2-3.
Step 2: Scan R's bounding box for other colors.
Inside R's rectangle, we find G and B. R must have been printed before G and B (they cover it).
Step 3: Scan G's bounding box for other colors.
Inside G's rectangle (rows 1-2, cols 1-2), cell (2,2) is B. So G must print before B.
Step 4: Scan B's bounding box for other colors.
Inside B's rectangle (rows 2-3, cols 2-3), every cell is B. No new dependencies.
Step 5: Topological sort on edges. No cycle found. Answer: true.
We can sort the colors: print R first (full grid), then G (covers part of R), then B (covers part of G and R). Valid!
The code
from collections import defaultdict, deque
def is_printable(target_grid: list[list[int]]) -> bool:
m, n = len(target_grid), len(target_grid[0])
top, bottom, left, right = {}, {}, {}, {}
colors = set()
for r in range(m):
for c in range(n):
color = target_grid[r][c]
colors.add(color)
if color not in top:
top[color] = r
bottom[color] = r
left[color] = c
right[color] = c
else:
top[color] = min(top[color], r)
bottom[color] = max(bottom[color], r)
left[color] = min(left[color], c)
right[color] = max(right[color], c)
graph = defaultdict(set)
in_degree = defaultdict(int)
for color in colors:
in_degree[color] = in_degree.get(color, 0)
for color in colors:
for r in range(top[color], bottom[color] + 1):
for c in range(left[color], right[color] + 1):
other = target_grid[r][c]
if other != color and other not in graph[color]:
graph[color].add(other)
in_degree[other] += 1
queue = deque(c for c in colors if in_degree[c] == 0)
processed = 0
while queue:
color = queue.popleft()
processed += 1
for neighbor in graph[color]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return processed == len(colors)
The solution has three phases. First, scan the grid to compute the bounding rectangle for each color by tracking the minimum and maximum row and column where that color appears. Second, build a dependency graph by scanning inside each color's bounding rectangle. If a different color appears at any cell within that rectangle, add an edge from the current color to the other color, meaning the current color must be printed first. Third, run Kahn's algorithm (topological sort via in-degree counting) on the dependency graph. If all colors can be processed (no cycle), the grid is achievable.
The use of sets for adjacency lists (graph[color] is a set) prevents duplicate edges. Without this, the in-degree count would be inflated and the topological sort would fail even on valid inputs.
The dependency graph has at most 60 nodes (one per color) since colors range from 1 to 60. The bottleneck is scanning the bounding rectangles, not the topological sort itself.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (all permutations) | O(C! * m * n) | O(m * n) |
| Topological sort | O(m * n * C) | O(C^2 + m * n) |
C is the number of distinct colors, m is the number of rows, and n is the number of columns.
For the topological sort approach, scanning the grid to build bounding boxes takes O(m * n). Building the dependency graph requires scanning each color's bounding rectangle, which in the worst case is the entire grid for each color, giving O(m * n * C). The topological sort itself runs in O(C^2) since there can be at most C^2 edges. Since C is at most 60, the dominant cost is the rectangle scanning.
The space comes from storing the dependency graph (up to C^2 edges) and the grid itself.
The building blocks
Bounding rectangle computation
For each color, you track four values: the minimum row, maximum row, minimum column, and maximum column where that color appears. This is a single pass through the grid. The same idea shows up in image processing (finding the bounding box of a connected region) and in computational geometry. It is a small, reusable building block that you can drill independently.
Topological sort with Kahn's algorithm
Kahn's algorithm peels off nodes with zero in-degree one layer at a time. If all nodes get processed, the graph is a DAG. If some remain, a cycle exists. This is the same algorithm used in Course Schedule, package dependency resolution, and build systems. The core loop is always the same: initialize in-degrees, seed the queue with zero-degree nodes, process and decrement, repeat.
Edge cases
Single color grid. Every cell is the same color. There are no dependencies, so the answer is always true.
Each cell is a different color. Every bounding rectangle is 1x1. No color's rectangle contains another color, so there are no edges. The answer is true.
Two colors that fully overlap. If color A's bounding box is the entire grid and color B's bounding box is also the entire grid, then A depends on B and B depends on A. That is a cycle, so the answer is false.
Colors that do not appear in the grid. The problem guarantees all colors in the grid are between 1 and 60. You only need to consider colors that actually appear, not all 60 possible values.
1x1 grid. A single cell with any color. Trivially true since one print covers it.
From understanding to recall
The insight here, turning a grid problem into a dependency graph, is a pattern you will see again and again. Whenever a problem asks "can this configuration be achieved by some ordering of operations," you should think about modeling the constraints as directed edges and checking for cycles.
The tricky part in an interview is not the topological sort itself. You have probably written Kahn's algorithm before. The tricky part is recognizing that you need it. The grid and the colorful rectangles distract you from the underlying structure. Once you see that each color's bounding rectangle defines what must come before it, the rest is mechanical.
Spaced repetition helps you bridge that gap. By practicing the bounding-rectangle-to-dependency-graph transformation alongside standard topological sort drills, you build the connection between "grid of overlapping shapes" and "dependency ordering" into your long-term memory. When you encounter a novel problem with the same structure, the pattern fires automatically.
Related posts
- Course Schedule - The classic topological sort problem, teaches Kahn's algorithm and DFS cycle detection from scratch
- Number of Islands - Grid traversal fundamentals that build the scanning intuition needed for bounding rectangle computation
- Sort Items by Groups Respecting Dependencies - A harder topological sort problem with layered dependency constraints