Strange Printer II - Video Solutions
LeetCode 1591. Strange Printer II
Strange Printer II - Video Solution
Watch 10 video solutions for Strange Printer II, a hard level problem involving Array, Graph, Topological Sort. This walkthrough by Happy Coding has 2,092 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
There is a strange printer with the following two special requirements:
- On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
- Once the printer has used a color for the above operation, the same color cannot be used again.
You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.
Return true if it is possible to print the matrix targetGrid, otherwise, return false.
Example 1:
Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]] Output: true
Example 2:
Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]] Output: true
Example 3:
Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]] Output: false Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
Constraints:
m == targetGrid.lengthn == targetGrid[i].length1 <= m, n <= 601 <= targetGrid[row][col] <= 60
Approach Overview
Problem Overview: You’re given a matrix where each value represents a color printed on a grid. A strange printer can print a solid rectangular block of a single color in one operation, possibly overwriting previous colors. The task is to determine if the final grid could be produced by printing each color in some order.
Approach 1: Simulation with Full Grid Construction (O(C * m * n) time, O(1) extra space)
This approach repeatedly checks whether a color can be printed at the current stage. First compute the bounding rectangle for every color in the matrix. A color can be printed if every cell in its rectangle is either that color or already cleared. When such a color is found, simulate "removing" it by marking its cells as cleared and continue scanning for the next valid color. If at some point no color can be removed but unprocessed colors remain, the configuration is impossible. This simulation mimics the reverse printing order and works well because the number of colors is small (≤ 60).
Approach 2: Topological Sort with Dependency Graph (O(C^2 + m * n) time, O(C^2) space)
A more structured solution models the constraints as a graph problem using graph and topological sort. For each color, compute its minimal bounding rectangle in the matrix. Scan that rectangle; if a different color appears inside it, the inner color must be printed before the outer color. Add a directed edge representing this dependency. After building the graph, perform a topological sort (Kahn’s algorithm or DFS cycle detection). If the dependency graph has a cycle, two colors require each other to be printed first, making the grid impossible to produce. If the graph is acyclic, a valid print order exists.
Recommended for interviews: The dependency graph with topological sorting is the approach most interviewers expect. It clearly models the constraints and demonstrates understanding of graph construction and cycle detection. The simulation method is easier to reason about and good for quickly validating the idea, but the graph solution scales better conceptually and communicates stronger algorithmic thinking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with Full Grid Construction | O(C * m * n) | O(1) | When the number of colors is small and you want a straightforward reverse-print simulation. |
| Topological Sort with Dependency Graph | O(C^2 + m * n) | O(C^2) | Best general solution. Clearly models color dependencies and detects cycles using graph algorithms. |