There is a strange printer with the following two special requirements:
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] <= 60Problem 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.
In this approach, each color acts as a node, and a directed edge exists between colors if one must be printed before another. This dependency graph can be resolved using topological sorting to determine if printing in a valid order is possible.
We capture the bounding box of every color and use dependency checking to ensure that all dependencies are satisfied before a color is printed. The challenge is that multiple passes might be needed before deciding the print-ability of a color.
Python
JavaScript
Time Complexity: O(m * n * k), where k is the number of unique colors.
Space Complexity: O(k) for storing the bounding boxes of all colors.
This approach involves simulating the required grid generation using possible sub-grids and checking if all requirements of the problem statement are met throughout the simulation.
C++ solution similar to other approaches but utilizes nested loops to verify dependencies of cell colors. It iteratively changes the grid to 0 for printed colors and checks until all are processed.
Time Complexity: O(m * n * k), where k is the number of unique colors.
Space Complexity: O(k) for tracking color ranges and processed colors.
| Approach | Complexity |
|---|---|
| Topological Sort with Dependency Graph | Time Complexity: O(m * n * k), where k is the number of unique colors. |
| Simulation with Full Grid Construction | Time Complexity: O(m * n * k), where k is the number of unique colors. |
| 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. |
LeetCode 1591. Strange Printer II • Happy Coding • 2,029 views views
Watch 9 more video solutions →Practice Strange Printer II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor