Strange Printer II

Hard
1697.

Strange Printer II

Strange Printer II is a hard coding problem on arrays, matrix and graph, asked in Amazon and Google interviews.

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.length
  • n == targetGrid[i].length
  • 1 <= m, n <= 60
  • 1 <= targetGrid[row][col] <= 60
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} targetGrid
 * @return {boolean}
 */
var isPrintable = function(targetGrid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Strange Printer II

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

  2. Hint 2

    If a cell inside colour a's bounding box shows colour b, then b must be printed after a. That gives a directed edge a → b.

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

  1. For each colour present, compute its bounding box (min/max row and column).
  2. For each colour a and each cell in its box with colour b != a, add the edge a → b (once) and increase b's in-degree.
  3. Run Kahn's algorithm: repeatedly remove a colour with in-degree 0 and decrement its successors.
  4. Return true if 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