LeetCode 1591 - Strange Printer II

In this problem, we are given a final colored matrix called targetGrid. We need to determine whether a strange printer could have produced this grid under two unusual restrictions.

leetcodehardarraygraph-theorytopological-sortmatrix

LeetCode Problem 1591

Difficulty: 🔴 Hard
Topics: Array, Graph Theory, Topological Sort, Matrix

Solution

Problem Understanding

In this problem, we are given a final colored matrix called targetGrid. We need to determine whether a strange printer could have produced this grid under two unusual restrictions.

The printer works as follows:

First, during one operation it can print a solid rectangular region using only one color. Every cell inside that rectangle becomes that color, regardless of what was previously there.

Second, once a color has been used in a print operation, that color can never be used again later.

The important consequence is that every color may only be printed exactly once, and that print must be a single rectangle.

The challenge is that rectangles may overlap. A later print operation can overwrite parts of an earlier rectangle. Therefore, even if a color appears in a non-rectangular shape in the final grid, it may still be valid because some cells could have been overwritten afterward.

For example, suppose color 1 originally printed a large rectangle covering the whole grid, and then color 2 printed a smaller rectangle inside it. The final appearance of color 1 would look like a border rather than a rectangle, but that is still achievable.

The input is an m x n matrix where:

  • m is the number of rows
  • n is the number of columns
  • each value represents a color

The task is to return:

  • true if some sequence of valid rectangle prints can produce the target grid
  • false otherwise

The constraints are small but non-trivial:

  • 1 <= m, n <= 60
  • colors range from 1 to 60

Since there are at most 60 distinct colors, graph-based solutions become practical.

Several edge cases are important:

A color may appear only once, which means its rectangle is just a single cell.

A color's bounding rectangle may contain other colors. This implies those other colors must have been printed later.

Cycles between color dependencies make printing impossible. For example:

1 2
2 1

Color 1 requires 2 to be printed later, but color 2 also requires 1 to be printed later. That creates a contradiction.

Another subtle case is when a color appears disconnected in the final grid. That alone does not make the configuration invalid, because overwritten regions can explain the gaps.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly search for a color whose current visible cells form a valid rectangle. If such a color exists, we can imagine printing it last, remove it from the grid, and continue recursively.

The process works like this:

  • For every remaining color, compute the smallest rectangle containing all of its visible cells.

  • Check whether every non-removed cell inside that rectangle is either:

  • the same color, or

  • already removed

  • If valid, remove that color and repeat.

This method is correct because if a color could have been printed last, then all cells in its rectangle that are still visible must belong to that color.

However, repeatedly scanning the entire grid for every color is expensive. In the worst case, we may repeatedly process the same cells many times.

Optimal Approach

The key insight is that printing order creates dependency relationships between colors.

Suppose color A has a bounding rectangle that contains a cell of color B.

That means:

  • A's rectangle must have been printed before B
  • otherwise A would overwrite B

Therefore:

A -> B

This becomes a directed graph problem.

We:

  1. Compute the bounding rectangle for every color.
  2. Examine every rectangle.
  3. If another color appears inside that rectangle, create a dependency edge.
  4. Perform topological sorting.
  5. If all colors can be topologically ordered, the grid is printable.
  6. If a cycle exists, printing is impossible.

This transforms the problem into cycle detection in a directed graph.

Approach Time Complexity Space Complexity Notes
Brute Force O((mn)^2) O(1) Repeatedly scans and removes printable colors
Optimal O(mn + C^2) O(C^2) Builds dependency graph and uses topological sort

Here, C is the number of colors, at most 60.

Algorithm Walkthrough

Step 1: Compute Bounding Rectangles

For every color, determine:

  • minimum row
  • maximum row
  • minimum column
  • maximum column

These define the smallest rectangle that contains all occurrences of the color.

We use four arrays because colors are limited to 1..60, making direct indexing efficient.

Step 2: Build Dependency Graph

For each color:

  1. Iterate through every cell inside its bounding rectangle.
  2. If a different color appears inside that rectangle:
  • the current color must be printed before the other color
  • add a directed edge

For example:

1 1 1
1 2 1
1 1 1

Color 1's rectangle contains color 2.

Therefore:

1 -> 2

meaning 1 must be printed earlier.

We also maintain indegree counts for topological sorting.

Step 3: Perform Topological Sort

We use Kahn's Algorithm.

  1. Insert every color with indegree 0 into a queue.
  2. Repeatedly remove a color from the queue.
  3. Decrease indegrees of its neighbors.
  4. If a neighbor reaches indegree 0, add it to the queue.

Count how many colors are processed.

Step 4: Check for Cycles

If all colors are processed, then the dependency graph is acyclic.

That means a valid printing order exists.

Otherwise, a cycle exists and printing is impossible.

Why it works

The critical invariant is:

If color A's rectangle contains color B, then A must be printed before B.

The dependency graph captures every such requirement. Any valid printing sequence must satisfy all directed edges. Therefore, the target grid is printable exactly when the graph is acyclic. Topological sorting determines whether such an ordering exists.

Python Solution

from typing import List
from collections import deque

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        rows = len(targetGrid)
        cols = len(targetGrid[0])

        MAX_COLOR = 61

        top = [rows] * MAX_COLOR
        bottom = [-1] * MAX_COLOR
        left = [cols] * MAX_COLOR
        right = [-1] * MAX_COLOR

        used_colors = set()

        # Compute bounding rectangles
        for r in range(rows):
            for c in range(cols):
                color = targetGrid[r][c]
                used_colors.add(color)

                top[color] = min(top[color], r)
                bottom[color] = max(bottom[color], r)
                left[color] = min(left[color], c)
                right[color] = max(right[color], c)

        # Build graph
        graph = [set() for _ in range(MAX_COLOR)]
        indegree = [0] * MAX_COLOR

        for color in used_colors:
            for r in range(top[color], bottom[color] + 1):
                for c in range(left[color], right[color] + 1):
                    other = targetGrid[r][c]

                    if other != color and other not in graph[color]:
                        graph[color].add(other)
                        indegree[other] += 1

        # Topological sort
        queue = deque()

        for color in used_colors:
            if indegree[color] == 0:
                queue.append(color)

        processed = 0

        while queue:
            color = queue.popleft()
            processed += 1

            for neighbor in graph[color]:
                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return processed == len(used_colors)

The implementation begins by scanning the grid once to compute the bounding rectangle for every color. Since colors are limited to 60, fixed-size arrays are more efficient than hash maps.

After the rectangles are known, the code builds the dependency graph. For every color, it examines all cells inside that color's rectangle. If another color appears there, then the current color must have been printed earlier.

The graph uses sets to avoid duplicate edges. Without sets, repeated occurrences of the same dependency would incorrectly inflate indegree counts.

Finally, Kahn's topological sorting algorithm determines whether the graph contains a cycle. If every color can be processed, the grid is printable.

Go Solution

package main

func isPrintable(targetGrid [][]int) bool {
	rows := len(targetGrid)
	cols := len(targetGrid[0])

	const MAX_COLOR = 61

	top := make([]int, MAX_COLOR)
	bottom := make([]int, MAX_COLOR)
	left := make([]int, MAX_COLOR)
	right := make([]int, MAX_COLOR)

	for i := 0; i < MAX_COLOR; i++ {
		top[i] = rows
		left[i] = cols
		bottom[i] = -1
		right[i] = -1
	}

	used := make([]bool, MAX_COLOR)

	// Compute bounding rectangles
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			color := targetGrid[r][c]
			used[color] = true

			if r < top[color] {
				top[color] = r
			}
			if r > bottom[color] {
				bottom[color] = r
			}
			if c < left[color] {
				left[color] = c
			}
			if c > right[color] {
				right[color] = c
			}
		}
	}

	graph := make([]map[int]bool, MAX_COLOR)
	for i := 0; i < MAX_COLOR; i++ {
		graph[i] = make(map[int]bool)
	}

	indegree := make([]int, MAX_COLOR)

	// Build dependency graph
	for color := 1; color < MAX_COLOR; color++ {
		if !used[color] {
			continue
		}

		for r := top[color]; r <= bottom[color]; r++ {
			for c := left[color]; c <= right[color]; c++ {
				other := targetGrid[r][c]

				if other != color && !graph[color][other] {
					graph[color][other] = true
					indegree[other]++
				}
			}
		}
	}

	// Topological sort
	queue := []int{}

	for color := 1; color < MAX_COLOR; color++ {
		if used[color] && indegree[color] == 0 {
			queue = append(queue, color)
		}
	}

	processed := 0

	for len(queue) > 0 {
		color := queue[0]
		queue = queue[1:]

		processed++

		for neighbor := range graph[color] {
			indegree[neighbor]--

			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	totalColors := 0
	for color := 1; color < MAX_COLOR; color++ {
		if used[color] {
			totalColors++
		}
	}

	return processed == totalColors
}

The Go implementation follows the same logic as the Python version. One notable difference is the use of map[int]bool to represent adjacency sets because Go does not have a built-in set type.

The queue for topological sorting is implemented using slices. Since the number of colors is at most 60, the overhead of slice shifting is negligible.

Integer overflow is not a concern because all counts remain very small.

Worked Examples

Example 1

[[1,1,1,1],
 [1,2,2,1],
 [1,2,2,1],
 [1,1,1,1]]

Step 1: Bounding Rectangles

Color Top Bottom Left Right
1 0 3 0 3
2 1 2 1 2

Step 2: Build Dependencies

For color 1, its rectangle covers the whole grid.

Inside that rectangle we see color 2.

Therefore:

1 -> 2

For color 2, its rectangle contains only 2.

No edges added.

Graph State

Color Outgoing Edges Indegree
1 {2} 0
2 {} 1

Step 3: Topological Sort

Initial queue:

[1]

Process 1:

  • remove edge to 2
  • indegree of 2 becomes 0

Queue becomes:

[2]

Process 2.

All colors processed successfully.

Result:

true

Example 2

[[1,1,1,1],
 [1,1,3,3],
 [1,1,3,4],
 [5,5,1,4]]

Bounding Rectangles

Color Rectangle
1 rows 0-3, cols 0-3
3 rows 1-2, cols 2-3
4 rows 2-3, cols 3-3
5 rows 3-3, cols 0-1

Dependencies

Color 1's rectangle contains:

  • 3
  • 4
  • 5

Edges:

1 -> 3
1 -> 4
1 -> 5

No cycles exist.

A valid order is:

1, 5, 3, 4

Result:

true

Example 3

[[1,2,1],
 [2,1,2],
 [1,2,1]]

Bounding Rectangles

Both colors occupy the entire grid.

Color Rectangle
1 whole grid
2 whole grid

Dependencies

Inside color 1's rectangle we see 2:

1 -> 2

Inside color 2's rectangle we see 1:

2 -> 1

This creates a cycle.

Topological sorting cannot process all colors.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(mn + C^2) Scan grid and process rectangles for each color
Space O(C^2) Dependency graph storage

The initial grid scan takes O(mn).

For dependency construction, each color examines its rectangle. Since there are at most 60 colors and the grid size is bounded by 60 x 60, the total work remains manageable.

The graph contains at most 60 * 60 edges, so topological sorting is effectively constant relative to the grid size.

Test Cases

sol = Solution()

# Example 1
assert sol.isPrintable([
    [1,1,1,1],
    [1,2,2,1],
    [1,2,2,1],
    [1,1,1,1]
]) == True  # nested rectangle

# Example 2
assert sol.isPrintable([
    [1,1,1,1],
    [1,1,3,3],
    [1,1,3,4],
    [5,5,1,4]
]) == True  # multiple dependencies without cycle

# Example 3
assert sol.isPrintable([
    [1,2,1],
    [2,1,2],
    [1,2,1]
]) == False  # cyclic dependency

# Single cell
assert sol.isPrintable([
    [1]
]) == True  # minimal grid

# Single color full grid
assert sol.isPrintable([
    [2,2],
    [2,2]
]) == True  # one rectangle only

# Two independent colors
assert sol.isPrintable([
    [1,1,2,2]
]) == True  # no overlap needed

# Simple cycle
assert sol.isPrintable([
    [1,2],
    [2,1]
]) == False  # direct cycle

# Layered rectangles
assert sol.isPrintable([
    [1,1,1],
    [1,2,1],
    [1,1,1]
]) == True  # inner rectangle overwrites outer

# Complex acyclic case
assert sol.isPrintable([
    [1,1,1,1],
    [1,2,2,1],
    [1,3,2,1],
    [1,1,1,1]
]) == True  # dependency chain

# Color appearing disconnected
assert sol.isPrintable([
    [1,1,1],
    [1,2,1],
    [1,1,1]
]) == True  # disconnected final shape is valid
Test Why
Example 1 Valid nested rectangle configuration
Example 2 Multiple dependencies without cycles
Example 3 Detects cyclic dependency
Single cell Smallest valid input
Single color full grid Trivial rectangle
Two independent colors No overlap interaction
Simple cycle Minimal impossible case
Layered rectangles Overwriting behavior
Complex acyclic case Multiple dependency levels
Color appearing disconnected Ensures overwrite logic works

Edge Cases

One important edge case is when a color appears in disconnected regions. A naive solution might incorrectly assume every color must already form a rectangle in the final grid. That is not true because later prints may overwrite portions of earlier rectangles. The implementation correctly handles this by using bounding rectangles and dependency analysis rather than shape validation.

Another critical edge case is cyclic overlap. If two colors each appear inside the other's bounding rectangle, both colors would need to be printed before the other, which is impossible. The topological sort naturally detects this situation because some nodes will never reach indegree zero.

A third subtle edge case occurs when a color appears only once. Its bounding rectangle degenerates into a single cell. Some implementations accidentally assume rectangles have positive width and height, causing indexing mistakes. This implementation handles single-cell rectangles correctly because all loops are inclusive and work even when top equals bottom or left equals right.