1
class Solution {
2
  // store each color's left, top, right, bottom
3
  private Set<Integer>[] graph;
4
  private int[] indegrees;
5
  private int[][] ranges;
6
  private boolean[] exists;
7
  private int m;
8
  private int n;
9
  private int maxColor = 60;
10

11
  public boolean isPrintable(int[][] targetGrid) {
12
    this.m = targetGrid.length;
13
    this.n = targetGrid[0].length;
14
    buildRanges(targetGrid);
15
    buildGraph(targetGrid);
16
    int count = 0;
17
    int totalCount = 0;
18
    Queue<Integer> queue = new LinkedList<>();
19
    for (int i = 1; i <= maxColor; i++) {
20
      if (exists[i]) {
21
        if (indegrees[i] == 0) {
22
          queue.offer(i);
23
        }
24
        totalCount++;
25
      }
26
    }
27
    while (!queue.isEmpty()) {
28
      count++;
29
      Integer current = queue.poll();
30
      for (Integer neighbor : graph[current]) {
31
        if (--indegrees[neighbor] == 0) {
32
          queue.offer(neighbor);
33
        }
34
      }
35
    }
36
    return count == totalCount;
37
  }
38

39
  private void buildRanges(int[][] targetGrid) {
40
    this.ranges = new int[maxColor + 1][4];
41
    for (int i = 1; i <= maxColor; i++) {
42
      ranges[i][0] = ranges[i][1] = Integer.MAX_VALUE;
43
      ranges[i][2] = ranges[i][3] = Integer.MIN_VALUE;
44
    }
45
    exists = new boolean[maxColor + 1];
46
    int max = 0;
47
    for (int i = 0; i < m; i++) {
48
      for (int j = 0; j < n; j++) {
49
        int color = targetGrid[i][j];
50
        exists[color] = true;
51
        max = Math.max(max, color);
52
        ranges[color][0] = Math.min(ranges[color][0], j);
53
        ranges[color][1] = Math.min(ranges[color][1], i);
54
        ranges[color][2] = Math.max(ranges[color][2], j);
55
        ranges[color][3] = Math.max(ranges[color][3], i);
56
      }
57
    }
58
    maxColor = max;
59
  }
60

61
  // TC O(n^3) to build graph
62
  private void buildGraph(int[][] targetGrid) {
63
    graph = new Set[maxColor + 1];
64
    indegrees = new int[maxColor + 1];
65
    for (int c = 1; c <= maxColor; c++) {
66
      if (exists[c]) {
67
        graph[c] = new HashSet<>();
68
        for (int i = ranges[c][1]; i <= ranges[c][3]; i++) {
69
          for (int j = ranges[c][0]; j <= ranges[c][2]; j++) {
70
            int other = targetGrid[i][j];
71
            if (other != c && !graph[c].contains(other)) {
72
              graph[c].add(other);
73
              indegrees[other]++;
74
            }
75
          }
76
        }
77
      }
78
    }
79
  }
80
}