We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Strange Printer II

Difficulty: Hard

Problem Description

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid. There is a strange printer that can print a solid rectangular pattern of a single color on the grid, covering up the existing colors. Once a color is used, it cannot be used again. Return true if it is possible to print the matrix targetGrid, otherwise return false.

Key Insights

  • The printer can only print rectangles of a single color.
  • Once a color is used, it cannot be reused, meaning overlapping colors in different areas must be handled carefully.
  • The color blocks must form rectangular shapes without breaking the continuity of the same colors in the grid.
  • If a color appears in a non-contiguous manner (i.e., separated by different colors), it is impossible to print the grid.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m + n)

Solution

To determine if it's possible to print the matrix targetGrid, we can use a depth-first search (DFS) or breadth-first search (BFS) to explore the connected components of the grid. Each color in the grid must form a contiguous rectangular area. We can maintain a record of the colors used and check if any color is reused. If a color appears in a non-contiguous manner, we can return false. If all colors are printed correctly, we return true.

  1. Iterate through each cell in the grid.
  2. For each unvisited cell, perform a BFS/DFS to mark all connected cells of the same color.
  3. Check if the connected component forms a rectangle by validating the coordinates of its corners.
  4. Ensure that no previously used color is reused.

Code Solutions

def isPrintable(targetGrid):
    from collections import defaultdict

    m, n = len(targetGrid), len(targetGrid[0])
    color_positions = defaultdict(list)

    # Record the positions of each color
    for i in range(m):
        for j in range(n):
            color_positions[targetGrid[i][j]].append((i, j))

    # Check each color's positions to ensure they form a rectangle
    for positions in color_positions.values():
        min_row = min(x[0] for x in positions)
        max_row = max(x[0] for x in positions)
        min_col = min(x[1] for x in positions)
        max_col = max(x[1] for x in positions)

        # Validate the rectangle formed by the current color
        for i in range(min_row, max_row + 1):
            for j in range(min_col, max_col + 1):
                if targetGrid[i][j] != targetGrid[min_row][min_col]:
                    return False

    return True
← Back to All Questions