This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1391. Check if There is a Valid Path in a Grid, the solution in this repository is mainly a union-find solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- Graph, BFS
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are leftValid, rightValid, upValid, downValid, hasValidPath.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- 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.
- 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:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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//Graph, BFS
02//Runtime: 428 ms, faster than 27.27% of C++ online submissions for Check if There is a Valid Path in a Grid.
03//Memory Usage: 72 MB, less than 100.00% of C++ online submissions for Check if There is a Valid Path in a Grid.
04class Solution {
05public:
06 vector<vector<bool>> visited;
07 vector<vector<int>> grid;
08 vector<int> right;
09 vector<int> left;
10 vector<int> up;
11 vector<int> down;
12 int m, n;
13
14 bool leftValid(int i, int j){
15 if(j >= 0 && !visited[i][j] && find(right.begin(), right.end(), grid[i][j]) != right.end())
16 return true;
17 return false;
18 };
19
20 bool rightValid(int i, int j){
21 if(j < n && !visited[i][j] && find(left.begin(), left.end(), grid[i][j]) != left.end())
22 return true;
23 return false;
24 };
25
26 bool upValid(int i, int j){
27 if(i >= 0 && !visited[i][j] && find(down.begin(), down.end(), grid[i][j]) != down.end())
28 return true;
29 return false;
30 };
31
32 bool downValid(int i, int j){
33 // cout << "downValid: " << i+1 << " " << j <<
34 if(i < m && !visited[i][j] && find(up.begin(), up.end(), grid[i][j]) != up.end())
35 return true;
36 return false;
37 };
38
39 bool hasValidPath(vector<vector<int>>& grid) {
40 this->grid = grid;
41 this->m = grid.size();
42 this->n = grid[0].size();
43 visited = vector<vector<bool>>(this->m, vector<bool>(this->n, false));
44
45 //can connect to which direction
46 // int tmp[3] = {1,4,6};
47 right = {1,4,6};
48 // right.assign(&tmp[0], &tmp[0]+3);
49 left = {1,3,5};
50 up = {2,5,6};
51 down = {2,3,4};
52
53 queue<vector<int>> q;
54
55 q.push({0,0});
56
57 while(!q.empty()){
58 vector<int> cur = q.front(); q.pop();
59 int i = cur[0], j = cur[1];
60 // cout << i << " " << j << endl;
61 visited[i][j] = true;
62
63 //we have reached the goal!
64 if(i == m-1 && j == n-1) return true;
65
66 switch(grid[i][j]){
67 case 1:
68 //left
69 if(leftValid(i, j-1)){
70 q.push({i, j-1});
71 }
72 //right
73 if(rightValid(i, j+1)){
74 q.push({i, j+1});
75 }
76 break;
77 case 2:
78 //up
79 if(upValid(i-1, j)){
80 q.push({i-1, j});
81 }
82 //down
83 if(downValid(i+1, j)){
84 q.push({i+1, j});
85 }
86 break;
87 case 3:
88 //left
89 if(leftValid(i, j-1)){
90 q.push({i, j-1});
91 }
92 //down
93 if(downValid(i+1, j)){
94 q.push({i+1, j});
95 }
96 break;
97 case 4:
98 //right
99 if(rightValid(i, j+1)){
100 q.push({i, j+1});
101 }
102 //down
103 if(downValid(i+1, j)){
104 q.push({i+1, j});
105 }
106 break;
107 case 5:
108 //up
109 if(upValid(i-1, j)){
110 q.push({i-1, j});
111 }
112 //left
113 if(leftValid(i, j-1)){
114 q.push({i, j-1});
115 }
116 break;
117 case 6:
118 //up
119 if(upValid(i-1, j)){
120 q.push({i-1, j});
121 }
122 //right
123 if(rightValid(i, j+1)){
124 q.push({i, j+1});
125 }
126 break;
127 }
128 }
129
130 return false;
131 }
132};
133
134//Graph, BFS
135//https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid/discuss/547371/Java-clean-BFS
136//Runtime: 472 ms, faster than 18.18% of C++ online submissions for Check if There is a Valid Path in a Grid.
137//Memory Usage: 66.3 MB, less than 100.00% of C++ online submissions for Check if There is a Valid Path in a Grid.
138class Solution {
139public:
140 bool hasValidPath(vector<vector<int>>& grid) {
141 int m = grid.size();
142 int n = grid[0].size();
143 vector<vector<bool>> visited = vector<vector<bool>>(m, vector<bool>(n, false));
144
145 vector<vector<vector<int>>> dirs ={
146 {{0,-1}, {0,1}},
147 {{-1,0}, {1,0}},
148 {{0,-1}, {1,0}},
149 {{0,1}, {1,0}},
150 {{0,-1}, {-1,0}},
151 {{-1,0}, {0,1}}
152 };
153
154 queue<vector<int>> q;
155
156 q.push({0,0});
157
158 while(!q.empty()){
159 vector<int> cur = q.front(); q.pop();
160 int i = cur[0], j = cur[1];
161 int type = grid[i][j]-1;
162 // cout << i << " " << j << endl;
163 visited[i][j] = true;
164
165 for(vector<int>& dir : dirs[type]){
166 //next position
167 int ni = i + dir[0], nj = j + dir[1];
168 //not valid position or already visited
169 if(ni < 0 || ni >= m || nj < 0 || nj >= n || visited[ni][nj]){
170 continue;
171 }
172 int ntype = grid[ni][nj]-1;
173 for(vector<int>& backdir : dirs[ntype]){
174 //the new position's street can connect to original position's street
175 if(ni + backdir[0] == i && nj + backdir[1] == j){
176 q.push({ni, nj});
177 }
178 }
179 }
180 }
181
182 return visited[m-1][n-1];
183 }
184};
185
186//disjoint set unit DSU
187//https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid/discuss/547229/Python-Union-Find
188//Runtime: 564 ms, faster than 25.21% of C++ online submissions for Check if There is a Valid Path in a Grid.
189//Memory Usage: 41.9 MB, less than 100.00% of C++ online submissions for Check if There is a Valid Path in a Grid.
190//time: O(m*n)*O(union find), space: O(m*n)
191class DSU{
192public:
193 vector<int> parent;
194
195 DSU(int size){
196 parent = vector<int>(size);
197 iota(parent.begin(), parent.end(), 0);
198 }
199
200 int find(int x){
201 if(parent[x] != x){
202 parent[x] = find(parent[x]);
203 }
204 return parent[x];
205 };
206
207 void unite(int x, int y){
208 parent[find(x)] = find(y);
209 }
210};
211
212class Solution {
213public:
214 int n;
215
216 int getId(int i, int j){
217 return 2*i*n + j;
218 };
219
220 bool hasValidPath(vector<vector<int>>& grid) {
221 int m = grid.size(), n = grid[0].size();
222 //used by getId
223 this->n = n;
224
225 //each grid has 4 points: its center, right, bottom, and bottom right
226 //we only use center, right and bottom
227 DSU dsu = DSU((2*m) * (2*n));
228
229 //this type of street can connect to top
230 set<int> top = {2,5,6};
231 set<int> bottom = {2,3,4};
232 set<int> left = {1,3,5};
233 set<int> right = {1,4,6};
234
235 for(int i = 0; i < m; i++){
236 for(int j = 0; j < n; j++){
237 int cur = grid[i][j];
238 //current grid's center
239 int curId = getId(2*i, 2*j);
240 int nextId;
241
242 if(top.find(cur) != top.end()){
243 nextId = getId(2*i-1, 2*j);
244 if(nextId >= 0){
245 //connect this grid's center and its top
246 //current grid's top is just its top grid's bottom
247 dsu.unite(nextId, curId);
248 }
249 }
250
251 if(bottom.find(cur) != bottom.end()){
252 nextId = getId(2*i+1, 2*j);
253 if(nextId >= 0){
254 dsu.unite(nextId, curId);
255 }
256 }
257
258 if(left.find(cur) != left.end()){
259 nextId = getId(2*i, 2*j-1);
260 if(nextId >= 0){
261 dsu.unite(nextId, curId);
262 }
263 }
264
265 if(right.find(cur) != right.end()){
266 nextId = getId(2*i, 2*j+1);
267 if(nextId >= 0){
268 dsu.unite(nextId, curId);
269 }
270 }
271 }
272 }
273
274 /*
275 if grid(0,0) and grid(m-1,n-1)'s center are
276 in the same disjoint set unit,
277 then they are connected
278 */
279 return dsu.find(0) == dsu.find(getId((m-1)*2, ((n-1)*2)));
280 }
281};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.