Is Strange Printer II easy or hard?

Strange Printer II is classified as a Hard problem because it requires recognizing hidden ordering constraints between colors. The challenge is converting a matrix printing rule into a graph dependency problem and correctly detecting cycles using topological sort.

Strange Printer II Python/Java solution

Python and Java implementations typically compute color bounding boxes, construct the dependency graph, and perform a topological sort using BFS (Kahn’s algorithm) or DFS cycle detection. The same logic applies across languages; only the graph representation and queue handling differ.

How to solve Strange Printer II in O(n)?

A strict O(n) solution is not typical because dependencies between colors must be checked. The closest practical complexity is O(C^2 + m*n) using a dependency graph and topological sorting. The grid is scanned to determine rectangle bounds and detect conflicting colors that create ordering constraints.

What is the best approach for Strange Printer II?

The most reliable approach builds a dependency graph between colors and performs a topological sort. Each color’s bounding rectangle is scanned to detect other colors inside it, creating directed edges that represent printing order constraints. If the graph contains no cycle, the grid is printable. This method runs in O(C^2 + m*n) time where C is the number of colors.

Is Strange Printer II asked at Google/Amazon/Meta?

Variants of matrix dependency and topological ordering problems appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may not always appear, the pattern of building a dependency graph from constraints and detecting cycles is common in system and algorithm interviews.

What data structure is used in Strange Printer II?

The core data structure is a directed graph representing dependencies between colors. Each node represents a color, and edges indicate printing order constraints. A queue or stack is then used during topological sorting to process nodes with zero incoming edges.

What is the time complexity of Strange Printer II?

The optimal graph-based solution runs in O(C^2 + m*n) time. Computing bounding rectangles takes O(m*n), building dependency edges costs up to O(C^2), and the topological sort is O(C + E). Space complexity is O(C^2) for the adjacency structure.

Description Hints 1 Solution Video 22:16

1591. Strange Printer II

Hard61.4% acceptance1 company

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.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Try thinking in reverse. Given the grid, how can you tell if a colour was painted last?

22:16

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution