Strange printer ii

Array Graph Theory Topological Sort Matrix

60.7% acceptance

Feb 25, 2026

691

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. 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 position (row, col). Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn is_printable(target_grid: Vec<Vec<i32>>) -> bool {
    let m = target_grid.len();
    let n = target_grid[0].len();
    let max_color = 61usize;

    // For each color, find bounding box
    let mut r_min = vec![m; max_color];
    let mut r_max = vec![0usize; max_color];
    let mut c_min = vec![n; max_color];
    let mut c_max = vec![0usize; max_color];

    for r in 0..m {
      for c in 0..n {
        let color = target_grid[r][c] as usize;
        r_min[color] = r_min[color].min(r);
        r_max[color] = r_max[color].max(r);
        c_min[color] = c_min[color].min(c);
        c_max[color] = c_max[color].max(c);
      }
    }

    // Build dependency graph: if color b is inside bounding box of a but a != b,
    // then a depends on b (b must be printed after a, i.e. b -> a)
    let mut deps = vec![vec![false; max_color]; max_color];
    for a in 1..max_color {
      if r_min[a] > m { continue; }
      for r in r_min[a]..=r_max[a] {
        for c in c_min[a]..=c_max[a] {
          let b = target_grid[r][c] as usize;
          if b != a {
            deps[a][b] = true; // a depends on b
          }
        }
      }
    }

    // Topological sort (Kahn's algorithm)
    let mut in_degree = vec![0u32; max_color];
    for a in 1..max_color {
      for b in 1..max_color {
        if deps[a][b] {
          in_degree[b] += 1;
        }
      }
    }

    // Wait — we need to detect cycles. If cycle exists → return false.
    // Actually let's use a simple cycle-detection via DFS.
    // Use 0=unvisited, 1=visiting, 2=done
    let mut state = vec![0u8; max_color];
    fn has_cycle(
      node: usize,
      deps: &Vec<Vec<bool>>,
      state: &mut Vec<u8>,
      max_color: usize,
    ) -> bool {
      if state[node] == 1 { return true; }
      if state[node] == 2 { return false; }
      state[node] = 1;
      for next in 1..max_color {
        if deps[node][next] && has_cycle(next, deps, state, max_color) {
          return true;
        }
      }
      state[node] = 2;
      false
    }

    for color in 1..max_color {
      if r_min[color] <= m && has_cycle(color, &deps, &mut state, max_color) {
        return false;
      }
    }
    true
  }
}