# Strange Printer II
**Difficulty:** HARD
[External](https://leetcode.com/problems/strange-printer-ii)
Canonical: https://scaleengineer.com/dsa/problems/strange-printer-ii
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Matrix, Graph
---
## 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:**

![](https://assets.glich.co/dsa/strange-printer-ii/image0.jpg) 

**Input:** targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/strange-printer-ii/image1.jpg) 

**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`

# Approaches
## Iterative Peeling Simulation
This approach simulates the printing process in reverse. It iteratively finds and 'peels off' colors that could have been printed last. A color can be peeled off if its rectangular area in the final grid doesn't contain any other colors that haven't been peeled off yet.
**Time:** O(C^2 * m * n), where C is the number of unique colors, and m, n are the grid dimensions. In the worst case, we might have C passes, and in each pass, we check up to C colors. Each check involves scanning a bounding box of up to size m*n. · **Space:** O(C + m*n). O(C) for storing bounding boxes and the set of peeled colors. The input grid takes O(m*n).
**Pros:** Conceptually simple and easy to understand.; Doesn't require explicit graph data structures.
**Cons:** Inefficient due to repeated scanning of grid regions.; The check for peelable colors is performed multiple times for the same color across different passes.
### Explanation
The core idea is to work backwards from the `targetGrid`. The last color printed must form a solid rectangle that isn't covered by any other color. We can identify such colors and conceptually 'remove' them. After removing a color, another color might become removable. We repeat this process until all colors are removed. If at any point we cannot find any color to remove while some colors still remain, it implies a cyclic dependency, and the grid is impossible to print.

**Algorithm:**
1.  First, determine the bounding box (minimum/maximum row/column) for each color present in the grid. This requires one pass through the grid.
2.  Maintain a set of colors that have been 'peeled' (removed).
3.  Enter a loop that continues as long as we can peel at least one color in a full pass.
4.  Inside the loop, iterate through all colors that have not yet been peeled.
5.  For each such color `c`, check if it's currently peelable. To do this, scan every cell within its pre-calculated bounding box. If all cells are either color `c` or a color that is already in the 'peeled' set, then color `c` is peelable.
6.  Keep a list of all colors that are found to be peelable in the current pass.
7.  If no colors were peelable in a pass but there are still unpeeled colors, it's impossible to proceed. This indicates a cycle, so we return `false`.
8.  Add all peelable colors from the pass to the 'peeled' set.
9.  If the loop finishes (meaning all colors have been successfully peeled), return `true`.

```java
class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        int m = targetGrid.length;
        int n = targetGrid[0].length;
        Map<Integer, int[]> bounds = new HashMap<>();

        // 1. Find bounding boxes for all colors
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int color = targetGrid[i][j];
                if (!bounds.containsKey(color)) {
                    bounds.put(color, new int[]{i, i, j, j}); // min_r, max_r, min_c, max_c
                } else {
                    int[] b = bounds.get(color);
                    b[0] = Math.min(b[0], i);
                    b[1] = Math.max(b[1], i);
                    b[2] = Math.min(b[2], j);
                    b[3] = Math.max(b[3], j);
                }
            }
        }

        Set<Integer> peeled = new HashSet<>();
        int peeledCount = 0;
        while (peeledCount < bounds.size()) {
            List<Integer> peelableInPass = new ArrayList<>();
            for (int color : bounds.keySet()) {
                if (peeled.contains(color)) {
                    continue;
                }
                if (isPeelable(color, bounds.get(color), targetGrid, peeled)) {
                    peelableInPass.add(color);
                }
            }

            if (peelableInPass.isEmpty()) {
                return false; // Cycle detected
            }

            for (int color : peelableInPass) {
                peeled.add(color);
            }
            peeledCount += peelableInPass.size();
        }

        return true;
    }

    private boolean isPeelable(int color, int[] b, int[][] grid, Set<Integer> peeled) {
        for (int i = b[0]; i <= b[1]; i++) {
            for (int j = b[2]; j <= b[3]; j++) {
                int currentColor = grid[i][j];
                if (currentColor != color && !peeled.contains(currentColor)) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Find the bounding box for each color in the grid.
- Initialize an empty set `peeled` to store colors that have been removed.
- Loop until all colors have been peeled:
  - Find all colors `c` that are not yet in `peeled` and are 'peelable'. A color is peelable if its bounding box only contains itself or colors already in `peeled`.
  - If no peelable colors are found in a pass, but unpeeled colors remain, return `false`.
  - Add all newly found peelable colors to the `peeled` set.
- If the loop completes, it means all colors were successfully peeled. Return `true`.

## Topological Sort on Dependency Graph
This approach models the problem as finding a valid ordering of operations. If color `B` appears inside the bounding box of color `A`, it implies that `A` must have been printed before `B`. This creates a dependency `A -> B`. A valid printing sequence is possible if and only if these dependencies do not form a cycle. We can build a dependency graph and check for cycles using a topological sort.
**Time:** O(C * m * n), where C is the number of unique colors, and m, n are grid dimensions. Finding bounds is O(m*n). Building the graph takes O(C*m*n) because for each of the C colors, we might scan the entire grid. Topological sort takes O(C^2) in the worst case for a dense graph. The dominant term is O(C*m*n). · **Space:** O(C^2 + m*n). O(C^2) for the adjacency list in the worst case. O(C) for other data structures like in-degree map, queue, and bounding box arrays. The input grid takes O(m*n).
**Pros:** Highly efficient and directly models the problem's constraints.; Correctly handles all cases, including complex cyclic dependencies.; Avoids redundant work by processing each dependency only once.
**Cons:** Requires understanding of graph theory, specifically topological sorting.; Implementation is more complex due to the need for graph data structures (adjacency list, in-degree map).
### Explanation
The problem can be reframed as a scheduling problem with dependencies. Each color corresponds to a task. A task `A` must be completed before task `B` if the print for color `B` must happen after the print for color `A`. This occurs if any cell within color `A`'s bounding rectangle is occupied by color `B` in the final grid.

This set of dependencies can be represented as a directed graph where colors are nodes and a dependency `A -> B` is a directed edge. The `targetGrid` is printable if and only if this dependency graph is a Directed Acyclic Graph (DAG). We can detect cycles in a directed graph using topological sorting (specifically, Kahn's algorithm).

**Algorithm:**
1.  **Find Bounding Boxes:** First, iterate through the `targetGrid` to find the minimum and maximum row and column for each color. This defines the bounding box for each color's print operation.
2.  **Build Dependency Graph:**
    *   Initialize an adjacency list to represent the graph and an array `inDegree` to store the number of incoming edges for each color (node).
    *   For each color `c`, iterate through all cells `(i, j)` within its bounding box.
    *   If a cell `(i, j)` contains a different color `d`, it implies `c` must be printed before `d`. Add a directed edge from `c` to `d`. Increment `inDegree[d]`. To avoid duplicate edges and redundant in-degree increments, we can use a set for each color's neighbors.
3.  **Topological Sort (Kahn's Algorithm):**
    *   Initialize a queue with all colors (nodes) that have an in-degree of 0. These are colors that can be printed first (or last in the reverse sequence).
    *   Keep a count of visited nodes.
    *   While the queue is not empty, dequeue a color `u`, increment the visited count, and process its neighbors.
    *   For each neighbor `v` of `u`, decrement its in-degree. If `v`'s in-degree becomes 0, enqueue it.
4.  **Check for Cycles:** After the algorithm finishes, if the count of visited nodes equals the total number of unique colors, it means a valid topological order was found (the graph is a DAG). Return `true`. Otherwise, a cycle was present, and it's impossible to print the grid, so return `false`.

```java
class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        int m = targetGrid.length;
        int n = targetGrid[0].length;
        List<Integer> colors = new ArrayList<>();
        int[] min_r = new int[61], max_r = new int[61], min_c = new int[61], max_c = new int[61];
        Arrays.fill(min_r, m); Arrays.fill(min_c, n);
        Arrays.fill(max_r, -1); Arrays.fill(max_c, -1);

        // 1. Find bounding boxes and unique colors
        boolean[] seen = new boolean[61];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int c = targetGrid[i][j];
                if (!seen[c]) {
                    seen[c] = true;
                    colors.add(c);
                }
                min_r[c] = Math.min(min_r[c], i);
                max_r[c] = Math.max(max_r[c], i);
                min_c[c] = Math.min(min_c[c], j);
                max_c[c] = Math.max(max_c[c], j);
            }
        }

        // 2. Build dependency graph
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (int c : colors) {
            adj.put(c, new HashSet<>());
            inDegree.put(c, 0);
        }

        for (int c1 : colors) {
            for (int i = min_r[c1]; i <= max_r[c1]; i++) {
                for (int j = min_c[c1]; j <= max_c[c1]; j++) {
                    int c2 = targetGrid[i][j];
                    if (c1 != c2) {
                        if (adj.get(c1).add(c2)) { // add returns true if element was not already present
                            inDegree.put(c2, inDegree.get(c2) + 1);
                        }
                    }
                }
            }
        }

        // 3. Topological Sort
        Queue<Integer> queue = new LinkedList<>();
        for (int c : colors) {
            if (inDegree.get(c) == 0) {
                queue.offer(c);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            count++;
            for (int v : adj.get(u)) {
                inDegree.put(v, inDegree.get(v) - 1);
                if (inDegree.get(v) == 0) {
                    queue.offer(v);
                }
            }
        }

        // 4. Check for cycles
        return count == colors.size();
    }
}
```
### Algorithm
- Determine the bounding box for each color.
- Construct a directed graph where colors are nodes. Add an edge from color `c1` to `c2` if `c2` appears within the bounding box of `c1`.
- Calculate the in-degree (number of incoming edges) for each node in the graph.
- Initialize a queue with all nodes having an in-degree of 0.
- While the queue is not empty, dequeue a node `u`, and for each of its neighbors `v`, decrement `v`'s in-degree. If `v`'s in-degree becomes 0, enqueue it.
- Count the number of nodes processed this way.
- If the count equals the total number of unique colors, the graph is acyclic, and the grid is printable. Otherwise, a cycle exists, and it's not printable.

# Solutions
### Java

```java
class Solution { public boolean isPrintable ( int [][] targetGrid ) { Map < Integer , int []> boundsMap = new HashMap < Integer , int []>(); int rows = targetGrid . length , columns = targetGrid [ 0 ]. length ; for ( int i = 0 ; i < rows ; i ++) { for ( int j = 0 ; j < columns ; j ++) { int color = targetGrid [ i ][ j ]; if (! boundsMap . containsKey ( color )) boundsMap . put ( color , new int []{ i , i , j , j }); else { int [] bounds = boundsMap . get ( color ); bounds [ 0 ] = Math . min ( bounds [ 0 ], i ); bounds [ 1 ] = Math . max ( bounds [ 1 ], i ); bounds [ 2 ] = Math . min ( bounds [ 2 ], j ); bounds [ 3 ] = Math . max ( bounds [ 3 ], j ); boundsMap . put ( color , bounds ); } } } Set < Integer > keySet = boundsMap . keySet (); Map < Integer , List < Integer >> greaterMap = new HashMap < Integer , List < Integer >>(); for ( int i = 0 ; i < rows ; i ++) { for ( int j = 0 ; j < columns ; j ++) { int color = targetGrid [ i ][ j ]; List < Integer > list = greaterMap . getOrDefault ( color , new ArrayList < Integer >()); for ( int key : keySet ) { if ( key != color ) { int [] bounds = boundsMap . get ( key ); if ( i >= bounds [ 0 ] && i <= bounds [ 1 ] && j >= bounds [ 2 ] && j <= bounds [ 3 ]) list . add ( key ); } } greaterMap . put ( color , list ); } } Map < Integer , Integer > indegreeMap = new HashMap < Integer , Integer >(); for ( int color : keySet ) { List < Integer > nextColors = greaterMap . getOrDefault ( color , new ArrayList < Integer >()); for ( int nextColor : nextColors ) { int indegree = indegreeMap . getOrDefault ( nextColor , 0 ) + 1 ; indegreeMap . put ( nextColor , indegree ); } } Set < Integer > visited = new HashSet < Integer >(); Queue < Integer > queue = new LinkedList < Integer >(); for ( int color : keySet ) { int indegree = indegreeMap . getOrDefault ( color , 0 ); if ( indegree == 0 ) { visited . add ( color ); queue . offer ( color ); } } while (! queue . isEmpty ()) { int color = queue . poll (); List < Integer > nextColors = greaterMap . getOrDefault ( color , new ArrayList < Integer >()); for ( int nextColor : nextColors ) { int indegree = indegreeMap . getOrDefault ( nextColor , 0 ) - 1 ; if ( indegree == 0 ) { indegreeMap . remove ( nextColor ); visited . add ( nextColor ); queue . offer ( nextColor ); } else indegreeMap . put ( nextColor , indegree ); } } return visited . size () == keySet . size (); } }
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/strange-printer-ii/ // Time: O(C^2 * MN) // Space: O(MN) class Solution { bool removable ( vector < vector < int >> & G , vector < vector < int >> & pos , int c ) { for ( int i = pos [ c ][ 0 ]; i <= pos [ c ][ 2 ]; ++ i ) { for ( int j = pos [ c ][ 1 ]; j <= pos [ c ][ 3 ]; ++ j ) { if ( G [ i ][ j ] != c && G [ i ][ j ] != 0 ) return false ; } } for ( int i = pos [ c ][ 0 ]; i <= pos [ c ][ 2 ]; ++ i ) { for ( int j = pos [ c ][ 1 ]; j <= pos [ c ][ 3 ]; ++ j ) G [ i ][ j ] = 0 ; } return true ; } public: bool isPrintable ( vector < vector < int >>& G ) { int M = G . size (), N = G [ 0 ]. size (); vector < vector < int >> pos ( 61 , { M , N , 0 , 0 }); unordered_set < int > colors , remove ; for ( int i = 0 ; i < M ; ++ i ) { for ( int j = 0 ; j < N ; ++ j ) { int c = G [ i ][ j ]; colors . insert ( c ); pos [ c ][ 0 ] = min ( pos [ c ][ 0 ], i ); pos [ c ][ 1 ] = min ( pos [ c ][ 1 ], j ); pos [ c ][ 2 ] = max ( pos [ c ][ 2 ], i ); pos [ c ][ 3 ] = max ( pos [ c ][ 3 ], j ); } } while ( colors . size ()) { for ( int c : colors ) { if ( removable ( G , pos , c )) remove . insert ( c ); } if ( remove . empty ()) return false ; for ( int c : remove ) colors . erase ( c ); remove . clear (); } return true ; } };
```