Minesweeper solution and explanation
Google
9 more videos on this problem
LeetCode 529. Minesweeper Explanation and Solutionhappygirlzt · 10:40 · 12K views
529. Minesweeper (python) (Leetcode Medium)Programming Live with Larry · 16:13 · 3K views
LeetCode 529. Minesweeper 中文解释 Chinese Versionhappygirlzt · 10:24 · 2K views
Leetcode #529 MinesweeperTom Spencer · 14:02 · 1K views
Leetcode 529(medium). Minesweeper扫雷【DFS/Recursion】中文AndroidBabies安卓大宝贝们 · 19:09 · 937 views
Leetcode 529: MinesweeperYouScaredMe · 9:14 · 857 views
Leetcode 529 Minesweeper (BFS)NovaAlgoML · 11:54 · 623 views
Minesweeper Solution LeetCode 529 | Super Easy | Rohan HaldiyaRohan · 20:51 · 302 views
LeetCode 529. MinesweeperTerence Chen · 20:26 · 267 views
529 Minesweeper(Python & DFS & full walkthru)AlgBreaker · 14:51 · 116 views
The problem
Let's play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
'M'represents an unrevealed mine,'E'represents an unrevealed empty square,'B'represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),- digit (
'1'to'8') represents how many mines are adjacent to this revealed square, and 'X'represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares ('M' or 'E').
Return the board after revealing this position according to the following rules:
- If a mine
'M'is revealed, then the game is over. You should change it to'X'. - If an empty square
'E'with no adjacent mines is revealed, then change it to a revealed blank'B'and all of its adjacent unrevealed squares should be revealed recursively. - If an empty square
'E'with at least one adjacent mine is revealed, then change it to a digit ('1'to'8') representing the number of adjacent mines. - Return the board when no more squares will be revealed.
Example 1:
Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0] Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
Example 2:
Input: board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2] Output: [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 50board[i][j]is either'M','E','B', or a digit from'1'to'8'.click.length == 20 <= clickr < m0 <= clickc < nboard[clickr][clickc]is either'M'or'E'.
Approach overview
Problem Overview: You’re given a Minesweeper board and a click position. If the clicked cell contains a mine, the game ends. Otherwise, reveal cells according to classic Minesweeper rules: show the number of adjacent mines, or recursively reveal neighboring cells when the count is zero.
Approach 1: Depth-First Search (DFS) Flood Fill (Time: O(m*n), Space: O(m*n))
This problem is essentially a flood-fill traversal on a matrix. When the clicked cell is empty ('E'), count mines in the 8 neighboring cells. If the count is non‑zero, update the cell with that number and stop expanding. If the count is zero, mark it as 'B' and recursively explore all 8 neighbors using Depth-First Search. Each cell is processed at most once, so the traversal runs in O(m*n) time with recursion stack up to O(m*n) in the worst case.
The key insight: only expand when the adjacent mine count is zero. That rule prevents unnecessary exploration and mirrors how the real Minesweeper game reveals empty regions.
Approach 2: Breadth-First Search (BFS) Expansion (Time: O(m*n), Space: O(m*n))
The same logic can be implemented iteratively with a queue using Breadth-First Search. Start by pushing the clicked cell into the queue. For each cell popped, count adjacent mines. If the count is greater than zero, write the number and stop expansion from that cell. If the count is zero, mark it as 'B' and enqueue all neighboring unrevealed cells.
BFS processes cells level by level and avoids recursion depth issues. The queue may temporarily hold many cells during large empty-region expansions, but overall complexity remains O(m*n) time and O(m*n) space because each cell enters the queue at most once.
This version is often preferred in production systems where recursion limits are a concern.
Recommended for interviews: Either DFS or BFS is acceptable since both represent the same flood-fill idea with O(m*n) complexity. Interviewers typically expect you to recognize the grid traversal pattern quickly and implement DFS first because it’s shorter. Explaining that BFS avoids recursion depth limits demonstrates stronger problem‑solving awareness.
Approach 1: Depth-First Search (DFS) Approach
This approach involves using Depth-First Search (DFS) to explore the board starting from the clicked position.
The idea is to recursively reveal empty squares ('E') with no adjacent mines, changing them to 'B', and stop when encountering a number or mine. A helper function is used to count the adjacent mines. If no mines are adjacent, DFS continues to explore the neighboring cells.
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
def dfs(r: int, c: int):
if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or board[r][c] != 'E':
return
mines = 0
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < len(board) and 0 <= nc < len(board[0]) and board[nr][nc] == 'M':
mines += 1
if mines > 0:
board[r][c] = str(mines)
else:
board[r][c] = 'B'
for dr, dc in directions:
dfs(r + dr, c + dc)
r, c = click
if board[r][c] == 'M':
board[r][c] = 'X'
else:
dfs(r, c)
return boardclass Solution {
private void dfs(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != 'E') {
return;
}
int mines = 0;
int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (int[] dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < board.length && nc < board[0].length && board[nr][nc] == 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = (char) ('0' + mines);
} else {
board[r][c] = 'B';
for (int[] dir : directions) {
dfs(board, r + dir[0], c + dir[1]);
}
}
}
public char[][] updateBoard(char[][] board, int[] click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
dfs(board, r, c);
}
return board;
}
}#include <vector>
using namespace std;
class Solution {
public:
void dfs(vector<vector<char>>& board, int r, int c) {
vector<vector<int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int m = board.size(), n = board[0].size();
if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] != 'E') return;
int mines = 0;
for (auto& dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'M')
mines++;
}
if (mines > 0) {
board[r][c] = '0' + mines;
} else {
board[r][c] = 'B';
for (auto& dir : directions) {
dfs(board, r + dir[0], c + dir[1]);
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
dfs(board, r, c);
}
return board;
}
};var updateBoard = function(board, click) {
const directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
function dfs(r, c) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] !== 'E') return;
let mines = 0;
for (let [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < board.length && nc < board[0].length && board[nr][nc] === 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = String(mines);
} else {
board[r][c] = 'B';
for (let [dr, dc] of directions) {
dfs(r + dr, c + dc);
}
}
}
const [r, c] = click;
if (board[r][c] === 'M') {
board[r][c] = 'X';
} else {
dfs(r, c);
}
return board;
};#include <stdio.h>
void dfs(char** board, int r, int c, int m, int n) {
if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] != 'E') return;
int mines = 0;
int directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (int i = 0; i < 8; i++) {
int nr = r + directions[i][0];
int nc = c + directions[i][1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'M')
mines++;
}
if (mines > 0) {
board[r][c] = '0' + mines;
} else {
board[r][c] = 'B';
for (int i = 0; i < 8; i++) {
dfs(board, r + directions[i][0], c + directions[i][1], m, n);
}
}
}
char** updateBoard(char** board, int boardSize, int* boardColSize, int* click, int clickSize, int* returnSize, int** returnColumnSizes) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
dfs(board, r, c, boardSize, *boardColSize);
}
*returnSize = boardSize;
*returnColumnSizes = boardColSize;
return board;
}public class Solution {
public char[][] UpdateBoard(char[][] board, int[] click) {
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
Dfs(board, r, c);
}
return board;
}
private void Dfs(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r >= board.Length || c >= board[0].Length || board[r][c] != 'E') return;
int mines = 0;
int[][] directions = new int[][] { new int[]{-1, -1}, new int[]{-1, 0}, new int[]{-1, 1},
new int[]{0, -1}, new int[]{0, 1},
new int[]{1, -1}, new int[]{1, 0}, new int[]{1, 1}};
foreach (var dir in directions) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < board.Length && nc < board[0].Length && board[nr][nc] == 'M')
mines++;
}
if (mines > 0) {
board[r][c] = (char)('0' + mines);
} else {
board[r][c] = 'B';
foreach (var dir in directions) {
Dfs(board, r + dir[0], c + dir[1]);
}
}
}
}This Python implementation uses DFS to explore the board from the given click position. It recursively reveals squares and counts adjacent mines. If a square has no adjacent mines, it continues to reveal adjacent squares.
Time Complexity: O(m * n) - In the worst scenario, the entire board could be processed.
Space Complexity: O(m * n) - Because of the recursion depth in DFS.
Approach 2: Breadth-First Search (BFS) Approach
This approach utilizes Breadth-First Search (BFS) to reveal the board starting from the clicked position. Use a queue to manage the cells that need to be visited.
Each cell that has no surrounding mines gets added to the queue for further exploration, while cells with adjacent mines are marked with the appropriate mine count.
from collections import deque
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
m, n = len(board), len(board[0])
r, c = click
if board[r][c] == 'M':
board[r][c] = 'X'
else:
queue = deque([(r, c)])
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
while queue:
r, c = queue.popleft()
mines = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'M':
mines += 1
if mines > 0:
board[r][c] = str(mines)
else:
board[r][c] = 'B'
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'E':
queue.append((nr, nc))
board[nr][nc] = '#' # mark as visited
return boardimport java.util.LinkedList;
import java.util.Queue;
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {r, c});
int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
while (!queue.isEmpty()) {
int[] point = queue.poll();
r = point[0];
c = point[1];
int mines = 0;
for (int[] dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = (char) ('0' + mines);
} else {
board[r][c] = 'B';
for (int[] dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'E') {
queue.add(new int[] {nr, nc});
board[nr][nc] = '#'; // mark as visited
}
}
}
}
}
return board;
}
}#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int m = board.size(), n = board[0].size();
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
queue<pair<int, int>> toVisit;
toVisit.emplace(r, c);
vector<vector<int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
while (!toVisit.empty()) {
auto [r, c] = toVisit.front();
toVisit.pop();
int mines = 0;
for (auto& dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = '0' + mines;
} else {
board[r][c] = 'B';
for (auto& dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'E') {
toVisit.emplace(nr, nc);
board[nr][nc] = '#'; // mark as visited
}
}
}
}
}
return board;
}
};var updateBoard = function(board, click) {
const directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
if (board[click[0]][click[1]] === 'M') {
board[click[0]][click[1]] = 'X';
} else {
const queue = [];
queue.push(click);
while (queue.length > 0) {
const [r, c] = queue.shift();
let mines = 0;
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && board[nr][nc] === 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = String(mines);
} else {
board[r][c] = 'B';
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && board[nr][nc] === 'E') {
queue.push([nr, nc]);
board[nr][nc] = '#'; // mark as visited
}
}
}
}
}
return board;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int row;
int col;
} Point;
void enqueue(Point* queue, int* tail, int row, int col) {
queue[(*tail)++] = (Point){row, col};
}
Point dequeue(Point* queue, int* head) {
return queue[(*head)++];
}
char** updateBoard(char** board, int boardSize, int* boardColSize, int* click, int clickSize, int* returnSize, int** returnColumnSizes) {
int directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int m = boardSize, n = *boardColSize;
Point queue[m * n]; // enough space for the maximum number of elements
int head = 0, tail = 0;
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
enqueue(queue, &tail, r, c);
while (head < tail) {
Point point = dequeue(queue, &head);
r = point.row;
c = point.col;
int mines = 0;
for (int i = 0; i < 8; i++) {
int nr = r + directions[i][0];
int nc = c + directions[i][1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = '0' + mines;
} else {
board[r][c] = 'B';
for (int i = 0; i < 8; i++) {
int nr = r + directions[i][0];
int nc = c + directions[i][1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'E') {
enqueue(queue, &tail, nr, nc);
board[nr][nc] = '#'; // mark as visited
}
}
}
}
}
*returnSize = m;
*returnColumnSizes = (int*)malloc(sizeof(int) * m);
for (int i = 0; i < m; i++) {
(*returnColumnSizes)[i] = n;
}
return board;
}using System.Collections.Generic;
public class Solution {
public char[][] UpdateBoard(char[][] board, int[] click) {
int m = board.Length, n = board[0].Length;
int r = click[0], c = click[1];
if (board[r][c] == 'M') {
board[r][c] = 'X';
} else {
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(new int[] {r, c});
int[][] directions = new int[][] { new int[]{-1, -1}, new int[]{-1, 0}, new int[]{-1, 1},
new int[]{0, -1}, new int[]{0, 1},
new int[]{1, -1}, new int[]{1, 0}, new int[]{1, 1}};
while (queue.Count > 0) {
var current = queue.Dequeue();
r = current[0];
c = current[1];
int mines = 0;
foreach (var dir in directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'M') {
mines++;
}
}
if (mines > 0) {
board[r][c] = (char)('0' + mines);
} else {
board[r][c] = 'B';
foreach (var dir in directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && board[nr][nc] == 'E') {
queue.Enqueue(new int[] {nr, nc});
board[nr][nc] = '#'; // mark as visited
}
}
}
}
}
return board;
}
}This Python example implements BFS by enqueuing cells to explore further. It processes the board using a queue, exploring directions from each point and computing surrounding mine counts before continuing.
Time Complexity: O(m * n) - Neck-deep exploration into cells might lead each being explored.
Space Complexity: O(m * n) - Queue management and space occupancy can hit asymptotic limits.
Approach 3: Default Approach
function updateBoard(board: string[][], click: number[]): string[][] {
const m = board.length;
const n = board[0].length;
const [i, j] = click;
const dfs = (i: number, j: number) => {
let cnt = 0;
for (let x = i - 1; x <= i + 1; ++x) {
for (let y = j - 1; y <= j + 1; ++y) {
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] === 'M') {
++cnt;
}
}
}
if (cnt > 0) {
board[i][j] = cnt.toString();
return;
}
board[i][j] = 'B';
for (let x = i - 1; x <= i + 1; ++x) {
for (let y = j - 1; y <= j + 1; ++y) {
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] === 'E') {
dfs(x, y);
}
}
}
};
if (board[i][j] === 'M') {
board[i][j] = 'X';
} else {
dfs(i, j);
}
return board;
}func updateBoard(board [][]byte, click []int) [][]byte {
m, n := len(board), len(board[0])
i, j := click[0], click[1]
var dfs func(i, j int)
dfs = func(i, j int) {
cnt := 0
for x := i - 1; x <= i+1; x++ {
for y := j - 1; y <= j+1; y++ {
if x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M' {
cnt++
}
}
}
if cnt > 0 {
board[i][j] = byte(cnt + '0')
return
}
board[i][j] = 'B'
for x := i - 1; x <= i+1; x++ {
for y := j - 1; y <= j+1; y++ {
if x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E' {
dfs(x, y)
}
}
}
}
if board[i][j] == 'M' {
board[i][j] = 'X'
} else {
dfs(i, j)
}
return board
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(m * n) - In the worst scenario, the entire board could be processed. Space Complexity: O(m * n) - Because of the recursion depth in DFS. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(m * n) - Neck-deep exploration into cells might lead each being explored. Space Complexity: O(m * n) - Queue management and space occupancy can hit asymptotic limits. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Concise recursive solution and typical interview implementation |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | When avoiding recursion limits or implementing iterative traversal |
Frequently asked questions
Is Minesweeper easy or hard?
Minesweeper is considered a medium difficulty problem. The main challenge is correctly implementing grid traversal with the Minesweeper reveal rules, especially handling the 8-direction neighbor checks and ensuring cells are not revisited.
Minesweeper Python/Java solution
Python and Java solutions typically implement DFS recursion or BFS using a queue. Both versions iterate through the 8 neighboring directions, count adjacent mines, and update the board accordingly. The complexity remains O(m*n) time and O(m*n) space regardless of language.
How to solve Minesweeper in O(n)?
Treat the board as a grid traversal problem and apply flood fill. Start from the clicked cell, count adjacent mines, and expand only when the count is zero. Using DFS recursion or a BFS queue ensures every cell is processed at most once, giving O(m*n) time and O(m*n) space complexity.
What is the best approach for Minesweeper?
The best approach is a flood-fill traversal using Depth-First Search (DFS) or Breadth-First Search (BFS). After a click, count mines in the 8 neighboring cells. If the count is zero, reveal neighbors recursively or through a queue. Both approaches run in O(m*n) time because each cell in the grid is processed at most once.
Is Minesweeper asked at Google/Amazon/Meta?
Grid traversal and flood-fill style problems like Minesweeper frequently appear in interviews at companies such as Google, Amazon, and Meta. Variations often test DFS/BFS reasoning on matrices, including island counting, region expansion, and game-board simulations.
What data structure is used in Minesweeper?
The core data structure is a 2D array (matrix) representing the board. DFS implementations rely on recursion and the call stack, while BFS implementations use a queue to process cells level by level. Both approaches repeatedly check the 8-directional neighbors around each cell.
What is the time complexity of Minesweeper?
The time complexity is O(m*n), where m and n are the board dimensions. In the worst case, the algorithm reveals every cell during a large empty-region expansion. Each cell is visited once while checking up to 8 neighbors, which keeps the complexity linear in the number of cells.