Strange Printer II — Solution in Python, Java & C++
Strange Printer II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and matrix.
Strange Printer II is a hard coding problem on arrays, matrix and graph, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Matrix, Graph, Topological Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A strange printer works under two rules:
- In one turn it prints a solid rectangle of a single colour, covering whatever colours were there before.
- Once a colour has been used, it can never be used again.
Given an m x n matrix targetGrid, where targetGrid[row][col] is the colour at that cell, return true if the printer can produce targetGrid starting from a blank page, and false otherwise.
Example 1
Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true
Explanation: Print the whole page in colour 1, then the 2 x 2 square in colour 2.
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: Colour 1's rectangle covers colour 2's cells and colour 2's covers colour 1's, so neither can be printed last.
Constraints
m == targetGrid.lengthn == targetGrid[i].length1 <= m, n <= 601 <= targetGrid[row][col] <= 60
Hints for Strange Printer II
Hint 1
Since every colour is printed once as a rectangle, that rectangle must at least cover the colour's bounding box — the smallest rectangle containing all its cells.
Hint 2
If a cell inside colour
a's bounding box shows colourb, thenbmust be printed aftera. That gives a directed edgea → b.Hint 3
The grid is printable exactly when these "must come before" edges contain no cycle — check with a topological sort (Kahn's algorithm).
How to solve Strange Printer II
Each colour's print must cover its bounding box, and anything visible inside that box but of another colour was printed later. Those ordering constraints form a directed graph on at most 60 colours; a valid printing order exists iff the graph is acyclic.
Approach
- For each colour present, compute its bounding box (min/max row and column).
- For each colour
aand each cell in its box with colourb != a, add the edgea → b(once) and increaseb's in-degree. - Run Kahn's algorithm: repeatedly remove a colour with in-degree 0 and decrement its successors.
- Return
trueif every colour present was removed.
Why it works
Necessity: printing a covers its whole box, so any other colour visible in the box must come later — the edges are forced, and a cycle makes printing impossible. Sufficiency: print colours in a topological order, each as exactly its bounding box. A cell showing colour b is covered last by b, because every other colour whose box contains the cell has an edge to b and is printed earlier.
Complexity
- Time —
O(C · m · n + C^2) for C ≤ 60 colours - Space —
O(C^2)
Pitfalls
- Add each edge only once, or in-degrees are inflated and Kahn's algorithm reports a false cycle.
- Only colours that actually appear take part — do not count absent colour numbers.
- Use the bounding box, not the cells themselves: a colour split into two separated regions still prints as one rectangle covering both.
Reference solution
Python
from collections import deque
from typing import List
def isPrintable(targetGrid: List[List[int]]) -> bool:
m, n = len(targetGrid), len(targetGrid[0])
top, bottom, left, right = [m] * 61, [-1] * 61, [n] * 61, [-1] * 61
for r in range(m):
for c in range(n):
v = targetGrid[r][c]
top[v] = min(top[v], r)
bottom[v] = max(bottom[v], r)
left[v] = min(left[v], c)
right[v] = max(right[v], c)
present = [v for v in range(1, 61) if bottom[v] != -1]
edge = [[False] * 61 for _ in range(61)]
indeg = [0] * 61
for a in present:
for r in range(top[a], bottom[a] + 1):
for c in range(left[a], right[a] + 1):
b = targetGrid[r][c]
if b != a and not edge[a][b]:
edge[a][b] = True
indeg[b] += 1
q = deque(v for v in present if indeg[v] == 0)
done = 0
while q:
a = q.popleft()
done += 1
for b in present:
if edge[a][b]:
indeg[b] -= 1
if indeg[b] == 0:
q.append(b)
return done == len(present)Java
public static boolean isPrintable(int[][] targetGrid) {
int m = targetGrid.length, n = targetGrid[0].length;
int[] top = new int[61], bottom = new int[61], left = new int[61], right = new int[61], indeg = new int[61];
Arrays.fill(top, m); Arrays.fill(bottom, -1); Arrays.fill(left, n); Arrays.fill(right, -1);
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
int v = targetGrid[r][c];
top[v] = Math.min(top[v], r); bottom[v] = Math.max(bottom[v], r);
left[v] = Math.min(left[v], c); right[v] = Math.max(right[v], c);
}
boolean[][] edge = new boolean[61][61];
int present = 0;
for (int a = 1; a <= 60; a++) {
if (bottom[a] == -1) continue;
present++;
for (int r = top[a]; r <= bottom[a]; r++) for (int c = left[a]; c <= right[a]; c++) {
int b = targetGrid[r][c];
if (b != a && !edge[a][b]) { edge[a][b] = true; indeg[b]++; }
}
}
int[] q = new int[61];
int head = 0, tail = 0;
for (int a = 1; a <= 60; a++) if (bottom[a] != -1 && indeg[a] == 0) q[tail++] = a;
while (head < tail) {
int a = q[head++];
for (int b = 1; b <= 60; b++) if (edge[a][b] && --indeg[b] == 0) q[tail++] = b;
}
return tail == present;
}C++
bool isPrintable(vector<vector<int>>& targetGrid) {
int m = targetGrid.size(), n = targetGrid[0].size();
vector<int> top(61, m), bottom(61, -1), left(61, n), right(61, -1), indeg(61, 0);
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
int v = targetGrid[r][c];
top[v] = min(top[v], r); bottom[v] = max(bottom[v], r);
left[v] = min(left[v], c); right[v] = max(right[v], c);
}
vector<vector<bool>> edge(61, vector<bool>(61, false));
int present = 0;
for (int a = 1; a <= 60; a++) {
if (bottom[a] == -1) continue;
present++;
for (int r = top[a]; r <= bottom[a]; r++) for (int c = left[a]; c <= right[a]; c++) {
int b = targetGrid[r][c];
if (b != a && !edge[a][b]) { edge[a][b] = true; indeg[b]++; }
}
}
vector<int> q;
for (int a = 1; a <= 60; a++) if (bottom[a] != -1 && indeg[a] == 0) q.push_back(a);
for (size_t h = 0; h < q.size(); h++) {
int a = q[h];
for (int b = 1; b <= 60; b++) if (edge[a][b] && --indeg[b] == 0) q.push_back(b);
}
return (int)q.size() == present;
}JavaScript
var isPrintable = function(targetGrid) {
var m = targetGrid.length, n = targetGrid[0].length;
var top = [], bottom = [], left = [], right = [], indeg = [], edge = [];
for (var v = 0; v <= 60; v++) {
top.push(m); bottom.push(-1); left.push(n); right.push(-1); indeg.push(0);
edge.push(new Array(61).fill(false));
}
for (var r = 0; r < m; r++) for (var c = 0; c < n; c++) {
var x = targetGrid[r][c];
top[x] = Math.min(top[x], r); bottom[x] = Math.max(bottom[x], r);
left[x] = Math.min(left[x], c); right[x] = Math.max(right[x], c);
}
var present = [];
for (var p = 1; p <= 60; p++) if (bottom[p] !== -1) present.push(p);
for (var i = 0; i < present.length; i++) {
var a = present[i];
for (var rr = top[a]; rr <= bottom[a]; rr++) for (var cc = left[a]; cc <= right[a]; cc++) {
var b = targetGrid[rr][cc];
if (b !== a && !edge[a][b]) { edge[a][b] = true; indeg[b]++; }
}
}
var q = [];
for (var j = 0; j < present.length; j++) if (indeg[present[j]] === 0) q.push(present[j]);
for (var h = 0; h < q.length; h++) {
for (var k = 0; k < present.length; k++) {
var d = present[k];
if (edge[q[h]][d] && --indeg[d] === 0) q.push(d);
}
}
return q.length === present.length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal