Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1591. Strange Printer II - Leetcode Solution

Code Implementation

class Solution:
    def isPrintable(self, targetGrid):
        from collections import defaultdict, deque
        n, m = len(targetGrid), len(targetGrid[0])
        colors = set()
        bounds = {}
        for i in range(n):
            for j in range(m):
                c = targetGrid[i][j]
                colors.add(c)
                if c not in bounds:
                    bounds[c] = [i, i, j, j]  # minRow, maxRow, minCol, maxCol
                else:
                    bounds[c][0] = min(bounds[c][0], i)
                    bounds[c][1] = max(bounds[c][1], i)
                    bounds[c][2] = min(bounds[c][2], j)
                    bounds[c][3] = max(bounds[c][3], j)
        # Build dependency graph
        graph = defaultdict(set)
        indegree = defaultdict(int)
        for c in colors:
            minR, maxR, minC, maxC = bounds[c]
            for i in range(minR, maxR+1):
                for j in range(minC, maxC+1):
                    if targetGrid[i][j] != c:
                        if targetGrid[i][j] not in graph[c]:
                            graph[c].add(targetGrid[i][j])
                            indegree[targetGrid[i][j]] += 1
        # Topological sort
        queue = deque([c for c in colors if indegree[c]==0])
        removed = set()
        while queue:
            c = queue.popleft()
            removed.add(c)
            for nei in graph[c]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)
        return len(removed) == len(colors)
      
class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        int n = targetGrid.size(), m = targetGrid[0].size();
        unordered_set<int> colors;
        unordered_map<int, vector<int>> bounds; // minRow, maxRow, minCol, maxCol
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int c = targetGrid[i][j];
                colors.insert(c);
                if (bounds.find(c) == bounds.end()) {
                    bounds[c] = {i, i, j, j};
                } else {
                    bounds[c][0] = min(bounds[c][0], i);
                    bounds[c][1] = max(bounds[c][1], i);
                    bounds[c][2] = min(bounds[c][2], j);
                    bounds[c][3] = max(bounds[c][3], j);
                }
            }
        }
        unordered_map<int, unordered_set<int>> graph;
        unordered_map<int, int> indegree;
        for (auto c : colors) {
            int minR = bounds[c][0], maxR = bounds[c][1], minC = bounds[c][2], maxC = bounds[c][3];
            for (int i = minR; i <= maxR; ++i) {
                for (int j = minC; j <= maxC; ++j) {
                    if (targetGrid[i][j] != c) {
                        if (graph[c].find(targetGrid[i][j]) == graph[c].end()) {
                            graph[c].insert(targetGrid[i][j]);
                            indegree[targetGrid[i][j]]++;
                        }
                    }
                }
            }
        }
        queue<int> q;
        for (auto c : colors)
            if (indegree[c] == 0) q.push(c);
        unordered_set<int> removed;
        while (!q.empty()) {
            int c = q.front(); q.pop();
            removed.insert(c);
            for (int nei : graph[c]) {
                indegree[nei]--;
                if (indegree[nei] == 0) q.push(nei);
            }
        }
        return removed.size() == colors.size();
    }
};
      
class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        int n = targetGrid.length, m = targetGrid[0].length;
        Set<Integer> colors = new HashSet<>();
        Map<Integer, int[]> bounds = new HashMap<>(); // minRow, maxRow, minCol, maxCol
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int c = targetGrid[i][j];
                colors.add(c);
                if (!bounds.containsKey(c)) {
                    bounds.put(c, new int[]{i, i, j, j});
                } else {
                    int[] arr = bounds.get(c);
                    arr[0] = Math.min(arr[0], i);
                    arr[1] = Math.max(arr[1], i);
                    arr[2] = Math.min(arr[2], j);
                    arr[3] = Math.max(arr[3], j);
                }
            }
        }
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        for (int c : colors) {
            int[] bound = bounds.get(c);
            int minR = bound[0], maxR = bound[1], minC = bound[2], maxC = bound[3];
            for (int i = minR; i <= maxR; ++i) {
                for (int j = minC; j <= maxC; ++j) {
                    int cc = targetGrid[i][j];
                    if (cc != c) {
                        if (!graph.containsKey(c)) graph.put(c, new HashSet<>());
                        if (!graph.get(c).contains(cc)) {
                            graph.get(c).add(cc);
                            indegree.put(cc, indegree.getOrDefault(cc, 0) + 1);
                        }
                    }
                }
            }
        }
        Queue<Integer> q = new LinkedList<>();
        for (int c : colors) {
            if (!indegree.containsKey(c) || indegree.get(c) == 0) q.add(c);
        }
        Set<Integer> removed = new HashSet<>();
        while (!q.isEmpty()) {
            int c = q.poll();
            removed.add(c);
            if (graph.containsKey(c)) {
                for (int nei : graph.get(c)) {
                    indegree.put(nei, indegree.get(nei) - 1);
                    if (indegree.get(nei) == 0) q.add(nei);
                }
            }
        }
        return removed.size() == colors.size();
    }
}
      
var isPrintable = function(targetGrid) {
    let n = targetGrid.length, m = targetGrid[0].length;
    let colors = new Set();
    let bounds = new Map(); // color: [minRow, maxRow, minCol, maxCol]
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            let c = targetGrid[i][j];
            colors.add(c);
            if (!bounds.has(c)) {
                bounds.set(c, [i, i, j, j]);
            } else {
                let arr = bounds.get(c);
                arr[0] = Math.min(arr[0], i);
                arr[1] = Math.max(arr[1], i);
                arr[2] = Math.min(arr[2], j);
                arr[3] = Math.max(arr[3], j);
            }
        }
    }
    let graph = new Map();
    let indegree = new Map();
    for (let c of colors) {
        let [minR, maxR, minC, maxC] = bounds.get(c);
        for (let i = minR; i <= maxR; ++i) {
            for (let j = minC; j <= maxC; ++j) {
                let cc = targetGrid[i][j];
                if (cc !== c) {
                    if (!graph.has(c)) graph.set(c, new Set());
                    if (!graph.get(c).has(cc)) {
                        graph.get(c).add(cc);
                        indegree.set(cc, (indegree.get(cc) || 0) + 1);
                    }
                }
            }
        }
    }
    let queue = [];
    for (let c of colors) {
        if (!indegree.has(c) || indegree.get(c) === 0) queue.push(c);
    }
    let removed = new Set();
    while (queue.length) {
        let c = queue.shift();
        removed.add(c);
        if (graph.has(c)) {
            for (let nei of graph.get(c)) {
                indegree.set(nei, indegree.get(nei) - 1);
                if (indegree.get(nei) === 0) queue.push(nei);
            }
        }
    }
    return removed.size === colors.size;
};

Problem Description

The "Strange Printer II" problem presents a targetGrid, a 2D matrix of integers, where each integer represents a color. The grid starts blank. You have a printer that can print a solid rectangle of any color, but each print can only cover a rectangle and will overwrite existing colors. The objective is to determine whether it is possible to print the targetGrid using a sequence of such rectangle prints, with the constraint that each color can be used any number of times, but the rectangle for each color must cover all instances of that color in the final grid in a single print (i.e., you cannot print the same color in two separate, non-overlapping rectangles). Key constraints:
  • Each color's print must be a single rectangle that covers all its cells in the grid.
  • The printer can overwrite previously printed colors.
  • You may print the colors in any order, but you must not print a color more than once.
  • The goal is to determine if some sequence of such prints can reproduce the targetGrid.

Thought Process

At first glance, one might consider simulating all possible printing orders or recursively trying all combinations. However, this quickly becomes infeasible due to the factorial number of color orderings. Instead, notice that the only way a color's rectangle can be printed is if all cells within its bounding rectangle are either already that color or will be overwritten by later prints. If another color appears inside a color's rectangle, that color must be printed after the current color to avoid being overwritten. This observation leads to the idea of dependency: if color B appears inside color A's rectangle, then B must be printed after A. This can be modeled as a dependency graph, and the problem reduces to checking if there is a valid topological ordering of the colors (i.e., no cycles in the dependency graph).

Solution Approach

To solve the problem efficiently, we use the following approach:
  1. Find Bounding Rectangles: For each color in the grid, determine the smallest rectangle (by finding min/max rows and columns) that covers all its cells.
  2. Build Dependency Graph: For each color, check every cell inside its bounding rectangle. If another color appears in this rectangle, add a directed edge from the current color to the other color in a dependency graph. This means the other color must be printed after the current color.
  3. Topological Sort: Perform a topological sort on the dependency graph. If it's possible to order the colors such that all dependencies are respected (i.e., no cycles), then the grid can be printed as required. Otherwise, it's impossible.
  • We use a hash map to store bounding rectangles and dependency relationships because lookups and updates are O(1).
  • We use a queue for the topological sort (Kahn's algorithm), ensuring efficient processing of nodes with zero dependencies.

Example Walkthrough

Let's consider the following targetGrid: 
  [
    [1,1,2],
    [1,1,2],
    [3,3,2]
  ]
  • Step 1: Bounding Rectangles
    - Color 1: covers rows 0-1, columns 0-1.
    - Color 2: covers rows 0-2, columns 2-2.
    - Color 3: covers rows 2-2, columns 0-1.
  • Step 2: Build Dependency Graph
    - For color 1, its rectangle contains only 1s, so no dependency.
    - For color 2, its rectangle includes (0,2), (1,2), (2,2), all are 2, so no dependency.
    - For color 3, its rectangle includes only 3s, so no dependency.
  • Step 3: Topological Sort
    - All indegrees are zero, so any order is possible.
    - Therefore, the answer is true.
If there was a cell of color 2 inside color 1's rectangle, we would have a dependency and need to check for cycles.

Time and Space Complexity

  • Brute-force approach: Trying all possible color orders is O(k!), where k is the number of colors, which is infeasible for even moderate k.
  • Optimized approach:
    • Finding bounding rectangles: O(n*m), where n and m are grid dimensions.
    • Building the dependency graph: O(k*n*m), but in practice much less since each cell is checked a constant number of times.
    • Topological sort: O(k + e), where k is the number of colors and e is the number of edges (dependencies).
    Total: O(n*m + k^2) time and O(k^2) space for the dependency graph.

Summary

The "Strange Printer II" problem is elegantly solved by recognizing it as a dependency ordering problem. By determining each color's bounding rectangle and building a dependency graph based on overlapping colors, we reduce the problem to a topological sort. If a valid order exists, the grid can be printed; otherwise, it's impossible. This approach is efficient, leverages classic graph algorithms, and illustrates the power of modeling real-world constraints as graph problems.