Let's make this one less mysterious. For 1559. Detect Cycles in 2D Grid, the solution in this repository is mainly a union-find 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: union-find, graph traversal.
The notes already sitting in the source point us in the right direction:
- dfs, detect cycle in undirected graph
- https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
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 getgid, isCyclicUtil, containsCycle, dfs, unite.
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 two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//dfs, detect cycle in undirected graph
02//https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
03//Runtime: 1872 ms, faster than 20.00% of C++ online submissions for Detect Cycles in 2D Grid.
04//Memory Usage: 245.8 MB, less than 20.00% of C++ online submissions for Detect Cycles in 2D Grid.
05class Solution {
06public:
07 int m, n;
08 unordered_map<char, unordered_map<int, unordered_set<int>>> graphs;
09 unordered_map<char, unordered_set<int>> nodes;
10
11 int getgid(int i, int j){
12 if(i < 0 || i >= m || j < 0 || j >= n) return -1;
13 return i*n + j;
14 }
15
16 bool isCyclicUtil(int v, unordered_map<int, unordered_set<int>>& graph, unordered_set<int>& visited, int parent){
17 visited.insert(v);
18
19 // cout << "visit " << v/n << ", " << v%n << endl;
20
21 for(const int& nei : graph[v]){
22 // cout << "look at " << nei/n << ", " << nei%n << endl;
23 if(visited.find(nei) == visited.end()){
24 if(isCyclicUtil(nei, graph, visited, v)){
25 // cout << nei/n << ", " << nei%n << " not visited and iscyclic" << endl;
26 return true;
27 }
28 }else if(nei != parent){
29 /*
30 consider the graph:
31 0<->1, 0<->2 and 2<->1
32 we go to 0, mark it as visited,
33 then go to 1, and mark it as visited,
34 then go to 2 from 1, then 2's parent is 1.
35 note that 2 has another nei, which is 0,
36 and 0 is not 2's parent,
37 so there is a cycle.
38 (2 and its neighbor 0 has common ancestor,
39 so 2 and 0 are already connected indirectly,
40 and 2 and 0 are also the neighbor to each other,
41 so there are 2 paths from 2 to 0,
42 so we can say there is a cycle)
43 */
44 // cout << nei/n << ", " << nei%n << " in rec stack" << endl;
45 return true;
46 }
47 }
48
49 return false;
50 }
51
52 bool containsCycle(vector<vector<char>>& grid) {
53 m = grid.size();
54 n = grid[0].size();
55
56 vector<vector<int>> dirs = {
57 {0, 1},
58 {0, -1},
59 {1, 0},
60 {-1, 0}
61 };
62
63 //build graph
64 for(int i = 0; i < m; ++i){
65 for(int j = 0; j < n; ++j){
66 int gid = getgid(i, j);
67 char c = grid[i][j];
68
69 for(vector<int>& dir : dirs){
70 int ni = i + dir[0];
71 int nj = j + dir[1];
72 int ngid = getgid(ni, nj);
73 if(ngid == -1) continue;
74 if(c == grid[ni][nj]){
75 // cout << "c: " << c << ", " << i << ", " << j << "<->" << ni << ", " << nj << endl;
76 graphs[c][gid].insert(ngid);
77 graphs[c][ngid].insert(gid);
78 nodes[c].insert(gid);
79 nodes[c].insert(ngid);
80 }
81 }
82 }
83 }
84
85 //check graphs corresponding to different chars
86 for(auto it = graphs.begin(); it != graphs.end(); ++it){
87 char c = it->first;
88 unordered_map<int, unordered_set<int>>& graph = it->second;
89
90 // cout << "look at " << c << ", nodes: " << nodes[c].size() << ", edges: " << graph.size() << endl;
91
92 if(nodes[c].size() < 4) continue;
93
94 unordered_set<int> visited;
95 unordered_set<int> recStack;
96
97 for(const int& node : nodes[c]){
98 // cout << "node: " << node/n << ", " << node%n << endl;
99 if(visited.find(node) != visited.end()) continue;
100 if(isCyclicUtil(node, graph, visited, -1)){
101 return true;
102 }
103 }
104 }
105
106 return false;
107 }
108};
109
110//dfs, detect cycle in undirected graph, cleaner
111//https://leetcode.com/problems/detect-cycles-in-2d-grid/discuss/805677/DFS-or-Simple-Explanation
112//Runtime: 832 ms, faster than 20.00% of C++ online submissions for Detect Cycles in 2D Grid.
113//Memory Usage: 98.4 MB, less than 20.00% of C++ online submissions for Detect Cycles in 2D Grid.
114class Solution {
115public:
116 int m, n;
117 vector<vector<bool>> visited;
118 vector<vector<int>> dirs;
119
120 bool dfs(int r, int c, int pr, int pc, vector<vector<char>>& grid){
121 visited[r][c] = true;
122
123 for(vector<int>& dir : dirs){
124 int nr = r + dir[0];
125 int nc = c + dir[1];
126 //neighbor must be valid
127 if(nr < 0 || nr >= m || nc < 0 || nc >= n)
128 continue;
129 //neighbor's color must be the same as cur's
130 if(grid[r][c] != grid[nr][nc])
131 continue;
132 if(!visited[nr][nc]){
133 if(dfs(nr, nc, r, c, grid)){
134 return true;
135 }
136 }else if(!(nr == pr && nc == pc)){
137 //neighbor is not parent
138 return true;
139 }
140 }
141
142 return false;
143 };
144
145 bool containsCycle(vector<vector<char>>& grid) {
146 m = grid.size();
147 n = grid[0].size();
148 visited = vector<vector<bool>>(m, vector<bool>(n, false));
149 dirs = {
150 {0,1},
151 {0,-1},
152 {1,0},
153 {-1,0}
154 };
155
156 for(int i = 0; i < m; ++i){
157 for(int j = 0; j < n; ++j){
158 if(!visited[i][j]){
159 if(dfs(i, j, -1, -1, grid)){
160 return true;
161 }
162 }
163 }
164 }
165
166 return false;
167 }
168};
169
170//Union find
171//https://www.geeksforgeeks.org/union-find/
172//Runtime: 596 ms, faster than 60.00% of C++ online submissions for Detect Cycles in 2D Grid.
173//Memory Usage: 45.6 MB, less than 20.00% of C++ online submissions for Detect Cycles in 2D Grid.
174class DSU{
175public:
176 vector<int> parent;
177
178 DSU(int n){
179 parent = vector<int>(n);
180 iota(parent.begin(), parent.end(), 0);
181 }
182
183 int find(int x){
184 if(parent[x] != x){
185 parent[x] = find(parent[x]);
186 }
187 return parent[x];
188 }
189
190 int unite(int x, int y){
191 //merge the larger into the smaller
192 if(x > y){
193 swap(x, y);
194 }
195
196 //they are already in the same union
197 if(parent[find(y)] == find(x)){
198 return -1;
199 }
200
201 //merge y into x
202 parent[find(y)] = find(x);
203 /*
204 this line is not:
205 parent[y] = find(x);
206 If so, it will give WA, 73 / 74 test cases passed.
207 */
208 return 0;
209 }
210};
211
212class Solution {
213public:
214 int m, n;
215
216 int getgid(int r, int c){
217 return r*n + c;
218 };
219
220 bool containsCycle(vector<vector<char>>& grid) {
221 m = grid.size();
222 n = grid[0].size();
223
224 DSU dsu(m*n);
225
226 for(int i = 0; i < m; ++i){
227 for(int j = 0; j < n; ++j){
228 if(i-1 >= 0 && grid[i][j] == grid[i-1][j]){
229 if(dsu.unite(getgid(i-1, j), getgid(i,j)))
230 return true;
231 }
232 if(j-1 >= 0 && grid[i][j] == grid[i][j-1]){
233 if(dsu.unite(getgid(i, j-1), getgid(i,j)))
234 return true;
235 }
236 }
237 }
238
239 return false;
240 }
241};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
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.