Strange Printer II - Practice Coding Problems

Strange Printer II - Problem

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.

Input & Output

Example 1 — Simple Valid Case

$ Input: targetGrid = [[1,1,1],[3,1,3]]

› Output: true

💡 Note: First print color 3 in rectangle covering entire grid, then print color 1 in rectangle covering positions (0,0) to (1,1). The overlapping region shows color 1 in final grid, so color 3 must be printed first.

Example 2 — Invalid Case

$ Input: targetGrid = [[1,2],[2,1]]

› Output: false

💡 Note: Color 1's bounding rectangle covers entire grid, as does color 2's. But both colors appear in each other's regions, creating a circular dependency that makes printing impossible.

Example 3 — Non-overlapping Colors

$ Input: targetGrid = [[1,1],[2,2]]

› Output: true

💡 Note: Colors 1 and 2 have non-overlapping bounding rectangles, so they can be printed in any order without conflicts.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Target grid with colored cells that must be achieved

Analysis

Find color dependencies based on overlapping rectangular regions

Output

Determine if valid printing order exists (no circular dependencies)

Key Takeaway

🎯 Key Insight: Model as dependency graph - cycles mean impossible printing order

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is to model this as a graph problem where colors have dependencies. If color A and color B overlap, and B appears in A's final region, then A must be printed before B. Use topological sorting to detect cycles - if a cycle exists, printing is impossible. Best approach uses topological sort with Time: O(k² × mn), Space: O(k² + mn) where k is number of unique colors.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(k! × m × n)	O(m × n)	Try all possible printing orders and simulate each one
Topological Sort Approach	O(k² × m × n)	O(k² + m × n)	Build dependency graph between colors and check for valid topological ordering

Brute Force Simulation — Algorithm Steps

Find all unique colors and their bounding rectangles
Generate all possible printing orders
For each order, simulate printing and check if result matches target

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Colors

Identify unique colors and their bounding rectangles

Try Orders

Generate all possible printing sequences

Simulate

Test each order to see if it produces the target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_COLORS 100
#define MAX_SIZE 100

typedef struct {
    int color;
    int top, left, bottom, right;
} ColorBound;

ColorBound bounds[MAX_COLORS];
int colorCount = 0;
int colors[MAX_COLORS];
int targetGrid[MAX_SIZE][MAX_SIZE];
int m, n;

int findColorIndex(int color) {
    for (int i = 0; i < colorCount; i++) {
        if (bounds[i].color == color) return i;
    }
    return -1;
}

bool simulatePrinting(int* order, int orderSize) {
    int grid[MAX_SIZE][MAX_SIZE];
    memset(grid, 0, sizeof(grid));
    
    for (int k = 0; k < orderSize; k++) {
        int colorIdx = findColorIndex(order[k]);
        if (colorIdx == -1) continue;
        
        ColorBound* bound = &bounds[colorIdx];
        for (int i = bound->top; i <= bound->bottom; i++) {
            for (int j = bound->left; j <= bound->right; j++) {
                grid[i][j] = bound->color;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != targetGrid[i][j]) {
                return false;
            }
        }
    }
    return true;
}

bool permute(int start, int size) {
    if (start == size) {
        return simulatePrinting(colors, size);
    }
    
    for (int i = start; i < size; i++) {
        int temp = colors[start];
        colors[start] = colors[i];
        colors[i] = temp;
        
        if (permute(start + 1, size)) {
            return true;
        }
        
        temp = colors[start];
        colors[start] = colors[i];
        colors[i] = temp;
    }
    return false;
}

bool solution(int grid[][MAX_SIZE], int rows, int cols) {
    m = rows;
    n = cols;
    memcpy(targetGrid, grid, sizeof(int) * rows * cols);
    
    colorCount = 0;
    
    // Find all colors and their bounding rectangles
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int color = grid[i][j];
            int idx = findColorIndex(color);
            
            if (idx == -1) {
                bounds[colorCount].color = color;
                bounds[colorCount].top = i;
                bounds[colorCount].left = j;
                bounds[colorCount].bottom = i;
                bounds[colorCount].right = j;
                colors[colorCount] = color;
                colorCount++;
            } else {
                if (i < bounds[idx].top) bounds[idx].top = i;
                if (j < bounds[idx].left) bounds[idx].left = j;
                if (i > bounds[idx].bottom) bounds[idx].bottom = i;
                if (j > bounds[idx].right) bounds[idx].right = j;
            }
        }
    }
    
    return permute(0, colorCount);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int grid[MAX_SIZE][MAX_SIZE];
    int rows = 0, cols = 0;
    
    // Basic JSON parsing
    char* ptr = strchr(line, '[');
    if (ptr) ptr++;
    
    while (ptr && *ptr) {
        if (*ptr == '[') {
            ptr++;
            cols = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[rows][cols++] = *ptr - '0';
                }
                ptr++;
            }
            rows++;
        }
        if (*ptr) ptr++;
    }
    
    bool result = solution(grid, rows, cols);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k! × m × n)

k! permutations of colors, each requiring O(mn) simulation time

✓ Linear Growth

Space Complexity

O(m × n)

Storage for grid simulation and color information

⚡ Linearithmic Space

15.4K Views

Medium Frequency

~35 min Avg. Time

680 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler