Let's make this one less mysterious. For 529. Minesweeper, the solution in this repository is mainly a graph traversal 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: graph traversal.
The notes already sitting in the source point us in the right direction:
- TLE
- 28 / 54 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The solution is organized around the main LeetCode entry point and a few local helpers.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- 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:
- 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//TLE
02//28 / 54 test cases passed.
03class Solution {
04public:
05 vector<vector<int>> dirs;
06
07 vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
08 int m = board.size(), n = board[0].size();
09 vector<vector<bool>> visited(m, vector<bool>(n, false));
10
11 queue<vector<int>> q;
12 vector<int> cur;
13 int curR, curC;
14
15 dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};
16
17 map<vector<int>, int> mCounts;
18
19 for(int i = 0; i < m; i++){
20 for(int j = 0; j < n; j++){
21 if(board[i][j] != 'M') continue;
22 for(vector<int>& dir : dirs){
23 int nextI = i + dir[0], nextJ = j + dir[1];
24 if(nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n){
25 mCounts[{nextI, nextJ}]++;
26 }
27 }
28 }
29 }
30
31 q.push(click);
32
33 while(!q.empty()){
34 cur = q.front(); q.pop();
35 curR = cur[0], curC = cur[1];
36 visited[curR][curC] = true;
37 if(board[curR][curC] == 'M'){
38 board[curR][curC] = 'X';
39 break;
40 }
41
42 // int mCount = 0;
43 // for(vector<int>& dir : dirs){
44 // int nextR = curR + dir[0];
45 // int nextC = curC + dir[1];
46 // if(nextR >= 0 && nextR < m && nextC >= 0 && nextC < n){
47 // if(board[nextR][nextC] == 'M'){
48 // mCount++;
49 // }
50 // }
51 // }
52
53 int mCount = mCounts[{curR,curC}];
54
55 if(mCount == 0){
56 board[curR][curC] = 'B';
57 //continue to reveal
58 for(vector<int>& dir : dirs){
59 int nextR = curR + dir[0];
60 int nextC = curC + dir[1];
61 if(nextR >= 0 && nextR < m && nextC >= 0 && nextC < n && !visited[nextR][nextC]){
62 q.push({nextR, nextC});
63 }
64 }
65 }else{
66 board[curR][curC] = ('0'+mCount);
67 //stop revealing
68 }
69 }
70
71 return board;
72 }
73};
74
75/*
76If set position as visited after it's popped from queue -> TLE, 28 / 54 test cases passed.
77Change to set position as visited before it's pushed into queue -> ...
78*/
79//Runtime: 60 ms, faster than 33.72% of C++ online submissions for Minesweeper.
80//Memory Usage: 12.8 MB, less than 100.00% of C++ online submissions for Minesweeper.
81class Solution {
82public:
83 vector<vector<int>> dirs;
84
85 vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
86 int m = board.size(), n = board[0].size();
87 vector<vector<bool>> visited(m, vector<bool>(n, false));
88
89 queue<vector<int>> q;
90 vector<int> cur;
91 int curR, curC;
92
93 dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};
94
95 /*
96 precalculate doesn't speedup
97 */
98// map<vector<int>, int> mCounts;
99
100// for(int i = 0; i < m; i++){
101// for(int j = 0; j < n; j++){
102// if(board[i][j] != 'M') continue;
103// for(vector<int>& dir : dirs){
104// int nextI = i + dir[0], nextJ = j + dir[1];
105// if(nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n){
106// mCounts[{nextI, nextJ}]++;
107// }
108// }
109// }
110// }
111
112 //set position as visited before pushing it into queue to speed up
113 visited[click[0]][click[1]] = true;
114 q.push(click);
115
116 while(!q.empty()){
117 cur = q.front(); q.pop();
118 curR = cur[0], curC = cur[1];
119 //set position as visited before pushing it into queue to speed up
120 // visited[curR][curC] = true;
121 if(board[curR][curC] == 'M'){
122 board[curR][curC] = 'X';
123 break;
124 }
125
126 int mCount = 0;
127 for(vector<int>& dir : dirs){
128 int nextR = curR + dir[0];
129 int nextC = curC + dir[1];
130 if(nextR >= 0 && nextR < m && nextC >= 0 && nextC < n){
131 if(board[nextR][nextC] == 'M'){
132 mCount++;
133 }
134 }
135 }
136
137 // int mCount = mCounts[{curR,curC}];
138
139 if(mCount == 0){
140 board[curR][curC] = 'B';
141 //continue to reveal
142 for(vector<int>& dir : dirs){
143 int nextR = curR + dir[0];
144 int nextC = curC + dir[1];
145 if(nextR >= 0 && nextR < m && nextC >= 0 && nextC < n && !visited[nextR][nextC]){
146 //set position as visited before pushing it into queue to speed up
147 visited[nextR][nextC] = true;
148 q.push({nextR, nextC});
149 }
150 }
151 }else{
152 board[curR][curC] = ('0'+mCount);
153 //stop revealing
154 }
155 }
156
157 return board;
158 }
159};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.