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.
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: 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
