Let's make this one less mysterious. For 1591. Strange Printer II, the solution in this repository is mainly a graph traversal solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- straight forward
- https://leetcode.com/problems/strange-printer-ii/discuss/854193/Python-Straight-Forward
- time: O(CCMN), space: O(4C)
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isPrintable, hasCycle, visited, recStack, indegree.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(CCMN), space: O(4C)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//straight forward
02//https://leetcode.com/problems/strange-printer-ii/discuss/854193/Python-Straight-Forward
03//Runtime: 80 ms, faster than 88.34% of C++ online submissions for Strange Printer II.
04//Memory Usage: 14.4 MB, less than 78.87% of C++ online submissions for Strange Printer II.
05//time: O(CCMN), space: O(4C)
06struct bound{
07 int up, down, left, right;
08
09 bound(){
10 up = left = INT_MAX;
11 down = right = INT_MIN;
12 }
13};
14
15class Solution {
16public:
17 bool isPrintable(vector<vector<int>>& targetGrid) {
18 unordered_map<int, bound> color2bound;
19
20 int m = targetGrid.size();
21 int n = targetGrid[0].size();
22
23 unordered_map<int, bool> filled;
24
25 for(int i = 0; i < m; ++i){
26 for(int j = 0; j < n; ++j){
27 int& c = targetGrid[i][j];
28 bound& b = color2bound[c];
29 b.left = min(b.left, j);
30 b.right = max(b.right, j);
31 b.up = min(b.up, i);
32 b.down = max(b.down, i);
33 filled[c] = false;
34 }
35 }
36
37 int color_count = color2bound.size();
38 while(color_count-- > 0){
39 //want to erase "color_count" colors
40 for(auto it = color2bound.begin(); it != color2bound.end(); ++it){
41 //find the color which is fillable
42 const int& c = it->first;
43 const bound& b = it->second;
44 if(filled[c]) continue;
45 bool fillable = true;
46 for(int i = b.up; i <= b.down; ++i){
47 for(int j = b.left; j <= b.right; ++j){
48 if(targetGrid[i][j] != 0 && targetGrid[i][j] != c){
49 fillable = false;
50 break;
51 }
52 }
53 if(!fillable) break;
54 }
55
56 if(fillable){
57 // cout << "fill " << c << endl;
58 for(int i = b.up; i <= b.down; ++i)
59 for(int j = b.left; j <= b.right; ++j)
60 targetGrid[i][j] = 0;
61 filled[c] = true;
62 break;
63 }
64 }
65 }
66
67 for(int i = 0; i < m; ++i){
68 for(int j = 0; j < n; ++j){
69 if(targetGrid[i][j] != 0){
70 return false;
71 }
72 }
73 }
74
75 return true;
76 }
77};
78
79//cycle detection
80//https://leetcode.com/problems/strange-printer-ii/discuss/854151/C%2B%2B-O(n3)-solution-checking-cycle-in-dependency-graph
81//https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
82//Runtime: 452 ms, faster than 24.32% of C++ online submissions for Strange Printer II.
83//Memory Usage: 22.8 MB, less than 40.22% of C++ online submissions for Strange Printer II.
84class Solution {
85public:
86 bool hasCycle(int cur, vector<unordered_set<int>>& graph,
87 vector<bool>& visited, vector<bool>& recStack){
88 if(!visited[cur]){
89 visited[cur] = true;
90 recStack[cur] = true;
91
92 for(const int& nei : graph[cur]){
93 if(recStack[nei]) return true;
94 if(!visited[nei] && hasCycle(nei, graph, visited, recStack))
95 return true;
96 }
97 }
98
99 recStack[cur] = false;
100
101 return false;
102 }
103
104 bool isPrintable(vector<vector<int>>& targetGrid) {
105 //valid range: [1,60]
106 vector<unordered_set<int>> color2dep(61);
107 int m = targetGrid.size();
108 int n = targetGrid[0].size();
109
110 for(int c = 1; c <= 60; ++c){
111 int left = INT_MAX, up = INT_MAX;
112 int right = INT_MIN, down = INT_MIN;
113
114 for(int i = 0; i < m; ++i){
115 for(int j = 0; j < n; ++j){
116 if(targetGrid[i][j] == c){
117 left = min(left, j);
118 right = max(right, j);
119 up = min(up, i);
120 down = max(down, i);
121 }
122 }
123 }
124
125 for(int i = up; i <= down; ++i){
126 for(int j = left; j <= right; ++j){
127 if(targetGrid[i][j] != c){
128 color2dep[c].insert(targetGrid[i][j]);
129 // cout << c << " depends on " << targetGrid[i][j] << endl;
130 }
131 }
132 }
133 }
134
135 vector<bool> visited(61, false);
136 vector<bool> recStack(61, false);
137 for(int c = 1; c <= 60; ++c){
138 // cout << "color " << c << endl;
139 if(!color2dep[c].empty() &&
140 !visited[c] && hasCycle(c, color2dep, visited, recStack)){
141 return false;
142 }
143 }
144
145 return true;
146 }
147};
148
149//topological sort
150//https://leetcode.com/problems/strange-printer-ii/discuss/854219/JavaTopological-Sort
151//Runtime: 500 ms, faster than 19.08% of C++ online submissions for Strange Printer II.
152//Memory Usage: 32.2 MB, less than 20.18% of C++ online submissions for Strange Printer II.
153class Solution {
154public:
155 bool isPrintable(vector<vector<int>>& targetGrid) {
156 //valid range: [1,60]
157 vector<unordered_set<int>> graph(61);
158 vector<unordered_set<int>> revgraph(61);
159 int m = targetGrid.size();
160 int n = targetGrid[0].size();
161
162 for(int c = 1; c <= 60; ++c){
163 int left = INT_MAX, up = INT_MAX;
164 int right = INT_MIN, down = INT_MIN;
165
166 for(int i = 0; i < m; ++i){
167 for(int j = 0; j < n; ++j){
168 if(targetGrid[i][j] == c){
169 left = min(left, j);
170 right = max(right, j);
171 up = min(up, i);
172 down = max(down, i);
173 }
174 }
175 }
176
177 for(int i = up; i <= down; ++i){
178 for(int j = left; j <= right; ++j){
179 if(targetGrid[i][j] != c){
180 //need to paint targetGrid[i][j] before c
181 graph[targetGrid[i][j]].insert(c);
182 revgraph[c].insert(targetGrid[i][j]);
183 }
184 }
185 }
186 }
187
188 //topological sort
189
190 //colors which have no dependencies, they should be painted first
191 queue<int> nodep;
192
193 vector<int> indegree(61);
194
195 for(int c = 1; c <= 60; ++c){
196 indegree[c] = revgraph[c].size();
197 }
198
199 for(int c = 1; c <= 60; ++c){
200 if(revgraph[c].size() == 0){
201 nodep.push(c);
202 }
203 }
204
205 unordered_set<int> visited;
206 while(!nodep.empty()){
207 int c = nodep.front(); nodep.pop();
208 //if already visited
209 if(!visited.insert(c).second) continue;
210
211 for(const int& nextc : graph[c]){
212 // cout << nextc << " : " << indegree[nextc] << " -> " << indegree[nextc]-1 << endl;
213 --indegree[nextc];
214 if(indegree[nextc] == 0){
215 nodep.push(nextc);
216 }
217 }
218 }
219
220 return visited.size() == 60;
221 }
222};Cost
Complexity
Time
O(CCMN), space: O(4C)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.