Strange Printer II

Hard

#1463Time: 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).

Algorithms

Topological Sort

Data structures

Array Matrix Graph

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

First, determine the bounding box (minimum/maximum row/column) for each color present in the grid. This requires one pass through the grid.
Maintain a set of colors that have been 'peeled' (removed).
Enter a loop that continues as long as we can peel at least one color in a full pass.
Inside the loop, iterate through all colors that have not yet been peeled.
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.
Keep a list of all colors that are found to be peelable in the current pass.
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.
Add all peelable colors from the pass to the 'peeled' set.
If the loop finishes (meaning all colors have been successfully peeled), return true.

1class Solution {2    public boolean isPrintable(int[][] targetGrid) {3        int m = targetGrid.length;4        int n = targetGrid[0].length;5        Map<Integer, int[]> bounds = new HashMap<>();6 7        // 1. Find bounding boxes for all colors8        for (int i = 0; i < m; i++) {9            for (int j = 0; j < n; j++) {10                int color = targetGrid[i][j];11                if (!bounds.containsKey(color)) {12                    bounds.put(color, new int[]{i, i, j, j}); // min_r, max_r, min_c, max_c13                } else {14                    int[] b = bounds.get(color);15                    b[0] = Math.min(b[0], i);16                    b[1] = Math.max(b[1], i);17                    b[2] = Math.min(b[2], j);18                    b[3] = Math.max(b[3], j);19                }20            }21        }22 23        Set<Integer> peeled = new HashSet<>();24        int peeledCount = 0;25        while (peeledCount < bounds.size()) {26            List<Integer> peelableInPass = new ArrayList<>();27            for (int color : bounds.keySet()) {28                if (peeled.contains(color)) {29                    continue;30                }31                if (isPeelable(color, bounds.get(color), targetGrid, peeled)) {32                    peelableInPass.add(color);33                }34            }35 36            if (peelableInPass.isEmpty()) {37                return false; // Cycle detected38            }39 40            for (int color : peelableInPass) {41                peeled.add(color);42            }43            peeledCount += peelableInPass.size();44        }45 46        return true;47    }48 49    private boolean isPeelable(int color, int[] b, int[][] grid, Set<Integer> peeled) {50        for (int i = b[0]; i <= b[1]; i++) {51            for (int j = b[2]; j <= b[3]; j++) {52                int currentColor = grid[i][j];53                if (currentColor != color && !peeled.contains(currentColor)) {54                    return false;55                }56            }57        }58        return true;59    }60}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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:

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

1class Solution {2    public boolean isPrintable(int[][] targetGrid) {3        int m = targetGrid.length;4        int n = targetGrid[0].length;5        List<Integer> colors = new ArrayList<>();6        int[] min_r = new int[61], max_r = new int[61], min_c = new int[61], max_c = new int[61];7        Arrays.fill(min_r, m); Arrays.fill(min_c, n);8        Arrays.fill(max_r, -1); Arrays.fill(max_c, -1);9 10        // 1. Find bounding boxes and unique colors11        boolean[] seen = new boolean[61];12        for (int i = 0; i < m; i++) {13            for (int j = 0; j < n; j++) {14                int c = targetGrid[i][j];15                if (!seen[c]) {16                    seen[c] = true;17                    colors.add(c);18                }19                min_r[c] = Math.min(min_r[c], i);20                max_r[c] = Math.max(max_r[c], i);21                min_c[c] = Math.min(min_c[c], j);22                max_c[c] = Math.max(max_c[c], j);23            }24        }25 26        // 2. Build dependency graph27        Map<Integer, Set<Integer>> adj = new HashMap<>();28        Map<Integer, Integer> inDegree = new HashMap<>();29        for (int c : colors) {30            adj.put(c, new HashSet<>());31            inDegree.put(c, 0);32        }33 34        for (int c1 : colors) {35            for (int i = min_r[c1]; i <= max_r[c1]; i++) {36                for (int j = min_c[c1]; j <= max_c[c1]; j++) {37                    int c2 = targetGrid[i][j];38                    if (c1 != c2) {39                        if (adj.get(c1).add(c2)) { // add returns true if element was not already present40                            inDegree.put(c2, inDegree.get(c2) + 1);41                        }42                    }43                }44            }45        }46 47        // 3. Topological Sort48        Queue<Integer> queue = new LinkedList<>();49        for (int c : colors) {50            if (inDegree.get(c) == 0) {51                queue.offer(c);52            }53        }54 55        int count = 0;56        while (!queue.isEmpty()) {57            int u = queue.poll();58            count++;59            for (int v : adj.get(u)) {60                inDegree.put(v, inDegree.get(v) - 1);61                if (inDegree.get(v) == 0) {62                    queue.offer(v);63                }64            }65        }66 67        // 4. Check for cycles68        return count == colors.size();69    }70}

Complexity

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).

Trade-offs

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).

Solutions

Solution

1class 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 (); } }

1// 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 ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem