Strange Printer II

For Strange Printer II, the clean solution is to reverse the printing process. Compute each color's smallest bounding rectangle, add a dependency when another color appears inside that rectangle, then run topological sort on the color graph. If every present color can be removed in that order, the grid is printable; if a cycle remains, one color blocks another forever.

Problem Statement

In Strange Printer II, each color can only be printed as one solid axis-aligned rectangle, and once a color is used, it cannot be printed again later. You are given a final targetGrid and need to decide whether some sequence of rectangle prints could create exactly that layout after later colors overwrite earlier ones.

The key observation is to reason backward instead of forward. A color that could have been printed last must fit inside its full bounding rectangle without needing any other unfinished color beneath it. That turns the matrix into a dependency graph between colors: if color A's rectangle contains color B, then A must be printed before B, and the answer is true only when those dependencies are acyclic.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: true

Example details omitted.

Example 3

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

Output: false

It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Constraints

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

Solution Approach

1. Build each color's bounding rectangle

Scan targetGrid and record the top, bottom, left, and right limits for every color that appears. In Strange Printer II, any valid print for a color must cover at least all of its cells in one rectangle, so this bounding box is forced. That converts scattered cells into a single region you can test for blocking colors.

2. Create dependency edges from rectangle overlap

For each present color c, walk every cell inside c's bounding rectangle. If you see another color d inside that area, then c must be printed before d, because d survives in the final grid after c's rectangle is laid down. Add a directed edge c -> d and track indegrees. This is the exact failure mode of the problem: overlapping rectangles can create a cycle where no color can be last.

3. Run topological sort on present colors

Push every color with indegree 0 into a queue and remove them in topological order, decreasing indegrees of their neighbors. If you can process all colors that appear in targetGrid, then the dependency graph is acyclic and the printer can realize the grid. If some colors remain with positive indegree, the rectangles mutually trap each other, so the answer is false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let C be the number of distinct colors, with C <= 60, and let the grid size be m x n. Computing bounding rectangles takes O(mn). Building edges checks each present color over its rectangle, which is O(Cmn) in the straightforward version and still practical because C is capped at 60. The topological sort is O(C + E), where E is the number of color dependencies. Space is O(C + E) for rectangles, indegrees, and the graph.

What Interviewers Usually Probe

• The hint about thinking in reverse is a strong signal to identify which color could have been printed last.
• The small color range up to 60 suggests modeling colors as graph nodes instead of treating every cell as a state.
• If overlapping rectangles seem to force ordering constraints, the expected pattern is indegree plus topological ordering.

Common Pitfalls or Variants

Common pitfalls

• Adding dependencies in the wrong direction is the most common bug; if color d appears inside color c's rectangle, then c must come before d.
• Forgetting to deduplicate edges can inflate indegrees and make an acyclic Strange Printer II instance look impossible.
• Trying to simulate forward painting cell by cell misses the one-rectangle-per-color rule and gets stuck on overwrite order.

Follow-up variants

• Replace topological sort with repeated elimination: remove any color whose rectangle currently contains only itself or already removed colors.
• Ask for one valid print order instead of just true or false; the topological order directly provides it when no cycle exists.
• Generalize the same rectangle-dependency idea to grids where symbols form layers and the task is to detect cyclic overwrite constraints.

FAQ

What is the main idea behind Strange Printer II?

Model each color by its bounding rectangle, then infer which colors must be printed earlier when another color appears inside that rectangle. The problem becomes cycle detection in a directed graph of color dependencies.

Why does topological sort work for this problem?

A color can be printed before every color that remains visible inside its forced rectangle. Those ordering constraints form a directed graph, and a valid printing sequence exists exactly when the graph has a topological order.

Why can I use the bounding rectangle of each color?

Because each color may be printed only once as a single rectangle. Any valid turn for that color must cover all of its final cells, so the minimal rectangle containing them is the only region that matters for dependency checks.

What makes Strange Printer II return false?

It returns false when the color dependencies form a cycle. In that case, each color requires another color to be printed first, so no color can legally be the last remaining layer.

Is graph indegree plus topological ordering the best pattern here?

Yes, it is the standard clean solution for this problem because the printer rules create ordering constraints between colors, not between individual cells. With at most 60 colors, the graph approach is both simpler and efficient enough.