1591. Strange Printer II Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

from collections import defaultdict, deque

def isPrintable(targetGrid):
    m, n = len(targetGrid), len(targetGrid[0])
    colors = defaultdict(lambda: [float('inf'), float('inf'), -float('inf'), -float('inf')])
    for r in range(m):
        for c in range(n):
            clr = targetGrid[r][c]
            colors[clr][0] = min(colors[clr][0], r)
            colors[clr][1] = min(colors[clr][1], c)
            colors[clr][2] = max(colors[clr][2], r)
            colors[clr][3] = max(colors[clr][3], c)

    def canColor(clr):
        r1, c1, r2, c2 = colors[clr]
        for r in range(r1, r2 + 1):
            for c in range(c1, c2 + 1):
                if targetGrid[r][c] != clr and not done[targetGrid[r][c]]:
                    return False
        return True

    done = {}
    colorList = list(colors.keys())
    while colorList:
        printable = False
        for clr in colorList[:]:
            if canColor(clr):
                done[clr] = True
                colorList.remove(clr)
                printable = True
                for r in range(colors[clr][0], colors[clr][2] + 1):
                    for c in range(colors[clr][1], colors[clr][3] + 1):
                        targetGrid[r][c] = 0
        if not printable:
            return False
    return True

JavaScript

function isPrintable(targetGrid) {
    const [m, n] = [targetGrid.length, targetGrid[0].length];
    const colors = new Map();

    for (let r = 0; r < m; ++r) {
        for (let c = 0; c < n; ++c) {
            const color = targetGrid[r][c];
            if (!colors.has(color)) {
                colors.set(color, [r, c, r, c]);
            } else {
                const [r1, c1, r2, c2] = colors.get(color);
                colors.set(color, [Math.min(r1, r), Math.min(c1, c), Math.max(r2, r), Math.max(c2, c)]);
            }
        }
    }

    const canColor = (color) => {
        const [r1, c1, r2, c2] = colors.get(color);
        for (let r = r1; r <= r2; ++r) {
            for (let c = c1; c <= c2; ++c) {
                if (targetGrid[r][c] !== color && !done.has(targetGrid[r][c])) {
                    return false;
                }
            }
        }
        return true;
    };

    const done = new Set();
    const colorList = Array.from(colors.keys());

    while (colorList.length) {
        let printable = false;
        for (const color of colorList.slice()) {
            if (canColor(color)) {
                done.add(color);
                colorList.splice(colorList.indexOf(color), 1);
                printable = true;
                for (let r = colors.get(color)[0]; r <= colors.get(color)[2]; ++r) {
                    for (let c = colors.get(color)[1]; c <= colors.get(color)[3]; ++c) {
                        targetGrid[r][c] = 0;
                    }
                }
            }
        }
        if (!printable) {
            return false;
        }
    }
    return true;
}

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.

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.

Java

public class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        int m = targetGrid.length, n = targetGrid[0].length;
        int[][] minRow = new int[61][2];
        int[][] minCol = new int[61][2];
        int[][] maxRow = new int[61][2];
        int[][] maxCol = new int[61][2];
        for (int i = 0; i <= 60; i++) {
            minRow[i][0] = m;
            minCol[i][0] = n;
            maxRow[i][0] = -1;
            maxCol[i][0] = -1;
        }

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int clr = targetGrid[r][c];
                minRow[clr][0] = Math.min(minRow[clr][0], r);
                minCol[clr][0] = Math.min(minCol[clr][0], c);
                maxRow[clr][0] = Math.max(maxRow[clr][0], r);
                maxCol[clr][0] = Math.max(maxCol[clr][0], c);
            }
        }

        boolean[] done = new boolean[61];
        boolean printable;
        do {
            printable = false;
            for (int clr = 1; clr <= 60; clr++) {
                if (!done[clr]) {
                    int r1 = minRow[clr][0], c1 = minCol[clr][0], r2 = maxRow[clr][0], c2 = maxCol[clr][0];
                    boolean canPrint = true;
                    for (int r = r1; r <= r2; r++) {
                        for (int c = c1; c <= c2; c++) {
                            if (targetGrid[r][c] != clr && !done[targetGrid[r][c]]) {
                                canPrint = false;
                                break;
                            }
                        }
                    }
                    if (canPrint) {
                        printable = true;
                        done[clr] = true;
                        for (int r = r1; r <= r2; r++) {
                            for (int c = c1; c <= c2; c++) {
                                targetGrid[r][c] = 0;
                            }
                        }
                    }
                }
            }
        } while (printable);

        for (int i = 1; i <= 60; i++) {
            if (!done[i]) return false;
        }
        return true;
    }
}

C++

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        int m = targetGrid.size(), n = targetGrid[0].size();
        vector<vector<int>> minRow(61, vector<int>(61, m)), minCol(61, vector<int>(61, n)), maxRow(61, vector<int>(61, -1)), maxCol(61, vector<int>(61, -1));

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                int color = targetGrid[r][c];
                minRow[color][0] = min(minRow[color][0], r);
                minCol[color][0] = min(minCol[color][0], c);
                maxRow[color][0] = max(maxRow[color][0], r);
                maxCol[color][0] = max(maxCol[color][0], c);
            }
        }

        set<int> done;
        bool printable;
        do {
            printable = false;
            for (int clr = 1; clr <= 60; ++clr) {
                if (done.count(clr) == 0) {
                    int r1 = minRow[clr][0], c1 = minCol[clr][0], r2 = maxRow[clr][0], c2 = maxCol[clr][0];
                    bool canPrint = true;

                    for (int r = r1; r <= r2 && canPrint; ++r) {
                        for (int c = c1; c <= c2; ++c) {
                            if (targetGrid[r][c] != clr && done.count(targetGrid[r][c]) == 0) {
                                canPrint = false;
                                break;
                            }
                        }
                    }

                    if (canPrint) {
                        printable = true;
                        done.insert(clr);
                        for (int r = r1; r <= r2; ++r) {
                            for (int c = c1; c <= c2; ++c) {
                                targetGrid[r][c] = 0;
                            }
                        }
                    }
                }
            }
        } while (printable);

        return done.size() == 60;
    }
};

Java solution follows similar logic by tracking dependencies and continuously printing only if conditions are met. The state of each color is updated interactively.

Complexity

Time Complexity: O(m * n * k), where k is the number of unique colors.
Space Complexity: O(k) for handling color information and done state.

Try this approach in the editor

Complexity comparison

Approach	Complexity
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 handling color information and done state.

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.

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.

Strange Printer II solution and explanation

The problem

Approach overview

Approach 1: Topological Sort with Dependency Graph

Approach 2: Simulation with Full Grid Construction

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Strange Printer II solution and explanation

The problem

Approach overview

Approach 1: Topological Sort with Dependency Graph

Approach 2: Simulation with Full Grid Construction

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems