Strange Printer II

Strange Printer II

What is this problem about?

Strange Printer II is a complex matrix-based problem that simulates a 2D printing process. In this version, you are given a target grid of colors, and you must determine if it's possible to print it. The printer only prints solid rectangles of a single color. Once a color is printed, it can be partially or fully covered by subsequent rectangles of other colors. The challenge is to find an ordering of colors such that the final result matches the given grid. If such an order exists, the grid is "printable."

Why is this asked in interviews?

This problem is a staple in Strange Printer II interview questions at companies like Amazon and Google. It is highly valued because it combines several advanced concepts: matrix traversal, bounding boxes, and dependency management. It specifically tests a candidate's ability to translate a visual overlapping problem into a graph problem. Success requires identifying that the overlaps create a "must-be-printed-after" relationship, which is a classic application of directed acyclic graphs (DAGs).

Algorithmic pattern used

The problem utilizes the Array, Matrix, Graph, Topological Sort interview pattern. The first step is to determine the bounding box (minimum and maximum row/column) for each color present in the grid. Any other color found within the bounding box of Color A must have been printed after Color A. This creates a directed edge in a dependency graph. Once the graph is built, you apply a Topological Sort (or Cycle Detection using DFS). If a cycle exists, it means the dependencies are contradictory, and the grid is impossible to print.

Example explanation

Consider a 3x3 grid: [1, 1, 2] [1, 1, 2] [2, 2, 2]

• Color 1's bounding box is (0,0) to (1,1). All cells are 1. No dependencies.
• Color 2's bounding box is (0,2) to (2,2). Wait, Color 2 also appears at (2,0) and (2,1). So its bounding box is actually (0,0) to (2,2)—the whole grid!
• Inside Color 2's bounding box, we see Color 1. This means Color 1 must have been printed after Color 2 to cover up those spots.
• If we had another color, say Color 3, inside Color 1's box, then Color 3 must be after Color 1. As long as there's no situation where A is after B and B is after A, we can print it.

Common mistakes candidates make

One frequent mistake is failing to calculate the bounding box correctly for each color. Another is not recognizing that a color can be completely covered by other colors, yet its bounding box still dictates its earliest possible printing turn. Many candidates also try to solve this using complex backtracking or recursion without realizing that the problem is fundamentally about order and dependencies, which is best handled by topological sorting.

Interview preparation tip

When you see a problem involving "layering" or "ordering" of operations where one can overwrite another, think of Topological Sort. Practice finding dependencies in 2D space. A good exercise is to manually draw out 3x4 grids with overlapping shapes and identify which color "must have come first." Also, brush up on Kahn’s algorithm and DFS-based cycle detection, as these are the two standard ways to implement a topological sort in an interview setting.