Skip to main content
Talentd

Strange Printer II - Solution & Explanation

HardArrayGraphTopological SortMatrix8 min readAsked at: Google
Practice this problem

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

Approach 1: Topological Sort with Dependency Graph

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Simulation with Full Grid Construction

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.

Code

C++Java

C++

Java

Complexity

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.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Topological Sort with Dependency Graph

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.

Simulation with Full Grid Construction

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.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation with Full Grid ConstructionO(C * m * n)O(1)When the number of colors is small and you want a straightforward reverse-print simulation.
Topological Sort with Dependency GraphO(C^2 + m * n)O(C^2)Best general solution. Clearly models color dependencies and detects cycles using graph algorithms.

Video Solution

LeetCode 1591. Strange Printer II • Happy Coding • 2,092 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Strange Printer II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Cycle in a Graph

Next

Sort Array by Moving Items to Empty Space