Strange Printer II

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.

Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

Constraints:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

Solution:

if color a contains color b, then we must fill color a then color b. This is pretty similar to to finish course b, you need to finish course a first.
So we can build a graph: color a pointed by all other colors contained in color a's rectangle.
topological sort(or dfs) to check whether we can reach all node. (Please refer to the idea behind 207. Course Schedule)

class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        List<Set<Integer>> graph = new ArrayList();
        int[] in = new int[61];
        for (int i = 0; i < 61; i ++) {
            graph.add(new HashSet());
        }
        for (int i = 1; i < 61; i ++) {
            search(graph, i, targetGrid, in);
        }
        // System.out.println(graph);
        // System.out.println(Arrays.toString(in));
        Deque<Integer> queue = new ArrayDeque();
        for (int i = 1; i < 61; i ++) {
            if (in[i] == 0) queue.offer(i);
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            // System.out.print(curr + ", ");
            count ++;
            
            for (int next : graph.get(curr)) {
                in[next] --;
                if (in[next] == 0) queue.offer(next);
            }
        }
        return count == 60;
    }
    
    private void search(List<Set<Integer>> graph, int color, int[][] targetGrid, int[] in) {
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
        for (int i = 0; i < targetGrid.length; i ++) {
            for (int j = 0; j < targetGrid[0].length; j ++) {
                if (targetGrid[i][j] == color) {
                    minX = Math.min(minX, i);
                    minY = Math.min(minY, j);
                    maxX = Math.max(maxX, i);
                    maxY = Math.max(maxY, j);
                }
            }
        }        
        if (minX == Integer.MAX_VALUE) return;
        for (int i = minX; i <= maxX; i ++) {
            for (int j = minY; j <= maxY; j ++) {
                if (targetGrid[i][j] != color) {
                    if (graph.get(targetGrid[i][j]).add(color)) {
                        in[color] ++;
                    }
                }
            }
        }
    }
}