1591. Strange Printer II LeetCode Solution
In this guide, you will get 1591. Strange Printer II LeetCode Solution with the best time and space complexity. The solution to Strange Printer II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Strange Printer II solution in C++
- Strange Printer II solution in Java
- Strange Printer II solution in Python
- Additional Resources

Problem Statement of Strange Printer II
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.
Example 1:
Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true
Example 2:
Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true
Example 3:
Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
Constraints:
m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60
Complexity Analysis
- Time Complexity: O(60 \cdot mn)
- Space Complexity: O(mn)
1591. Strange Printer II LeetCode Solution in C++
enum class State { kInit, kVisiting, kVisited };
class Solution {
public:
bool isPrintable(vector<vector<int>>& targetGrid) {
constexpr int kMaxColor = 60;
const int m = targetGrid.size();
const int n = targetGrid[0].size();
// graph[u] := {v1, v2} means v1 and v2 cover u
vector<unordered_set<int>> graph(kMaxColor + 1);
for (int color = 1; color <= kMaxColor; ++color) {
// Get the rectangle of the current color.
int minI = m;
int minJ = n;
int maxI = -1;
int maxJ = -1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (targetGrid[i][j] == color) {
minI = min(minI, i);
minJ = min(minJ, j);
maxI = max(maxI, i);
maxJ = max(maxJ, j);
}
// Add any color covering the current as the children.
for (int i = minI; i <= maxI; ++i)
for (int j = minJ; j <= maxJ; ++j)
if (targetGrid[i][j] != color)
graph[color].insert(targetGrid[i][j]);
}
vector<State> states(kMaxColor + 1);
for (int color = 1; color <= kMaxColor; ++color)
if (hasCycle(graph, color, states))
return false;
return true;
}
private:
bool hasCycle(const vector<unordered_set<int>>& graph, int u,
vector<State>& states) {
if (states[u] == State::kVisiting)
return true;
if (states[u] == State::kVisited)
return false;
states[u] = State::kVisiting;
for (const int v : graph[u])
if (hasCycle(graph, v, states))
return true;
states[u] = State::kVisited;
return false;
}
};
/* code provided by PROGIEZ */
1591. Strange Printer II LeetCode Solution in Java
enum State { kInit, kVisiting, kVisited }
class Solution {
public boolean isPrintable(int[][] targetGrid) {
final int kMaxColor = 60;
final int m = targetGrid.length;
final int n = targetGrid[0].length;
// graph[u] := {v1, v2} means v1 and v2 cover u
Set<Integer>[] graph = new HashSet[kMaxColor + 1];
for (int color = 1; color <= kMaxColor; ++color) {
// Get the rectangle of the current color.
int minI = m;
int minJ = n;
int maxI = -1;
int maxJ = -1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (targetGrid[i][j] == color) {
minI = Math.min(minI, i);
minJ = Math.min(minJ, j);
maxI = Math.max(maxI, i);
maxJ = Math.max(maxJ, j);
}
// Add any color covering the current as the children.
graph[color] = new HashSet<>();
for (int i = minI; i <= maxI; ++i)
for (int j = minJ; j <= maxJ; ++j)
if (targetGrid[i][j] != color) {
graph[color].add(targetGrid[i][j]);
}
}
State[] states = new State[kMaxColor + 1];
for (int color = 1; color <= kMaxColor; ++color)
if (hasCycle(graph, color, states))
return false;
return true;
}
private boolean hasCycle(Set<Integer>[] graph, int u, State[] states) {
if (states[u] == State.kVisiting)
return true;
if (states[u] == State.kVisited)
return false;
states[u] = State.kVisiting;
for (int v : graph[u])
if (hasCycle(graph, v, states))
return true;
states[u] = State.kVisited;
return false;
}
}
// code provided by PROGIEZ
1591. Strange Printer II LeetCode Solution in Python
from enum import Enum
class State(Enum):
kInit = 0
kVisiting = 1
kVisited = 2
class Solution:
def isPrintable(self, targetGrid: list[list[int]]) -> bool:
kMaxColor = 60
m = len(targetGrid)
n = len(targetGrid[0])
# graph[u] := {v1, v2} means v1 and v2 cover u
graph = [set() for _ in range(kMaxColor + 1)]
for color in range(1, kMaxColor + 1):
# Get the rectangle of the current color.
minI = m
minJ = n
maxI = -1
maxJ = -1
for i in range(m):
for j in range(n):
if targetGrid[i][j] == color:
minI = min(minI, i)
minJ = min(minJ, j)
maxI = max(maxI, i)
maxJ = max(maxJ, j)
# Add any color covering the current as the children.
for i in range(minI, maxI + 1):
for j in range(minJ, maxJ + 1):
if targetGrid[i][j] != color:
graph[color].add(targetGrid[i][j])
states = [State.kInit] * (kMaxColor + 1)
def hasCycle(u: int) -> bool:
if states[u] == State.kVisiting:
return True
if states[u] == State.kVisited:
return False
states[u] = State.kVisiting
if any(hasCycle(v) for v in graph[u]):
return True
states[u] = State.kVisited
return False
return not (any(hasCycle(i) for i in range(1, kMaxColor + 1)))
# code by PROGIEZ
Additional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.