Last updated on February 4th, 2025 at 12:58 am
Here, we see a Minesweeper LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Breadth-First Search, Depth-First Search
Companies
Amazon
Level of Question
Medium
Minesweeper LeetCode Solution
Table of Contents
1. Problem Statement
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”]]
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Islands”. This pattern is commonly used to solve problems that involve traversing a grid (2D matrix) to explore connected components, such as finding islands, regions, or clusters. The problem involves recursively or iteratively exploring adjacent cells in a grid, which is characteristic of the “Islands” pattern.
3. Code Implementation in Different Languages
3.1 Minesweeper C++
class Solution {
public:
int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};
bool isValid(vector<vector<char>>& board, int i, int j) {
return (i >= 0 && j >= 0 && i < board.size() && j < board[0].size());
}
int hasAdjacentMine(vector<vector<char>>& board, int i, int j) {
int count = 0;
for (int k=0; k<8; k++) {
int I = i + dx[k];
int J = j + dy[k];
if (isValid(board, I, J) && board[I][J] == 'M')
count++;
}
return count;
}
void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int i, int j) {
if (min(i, j) < 0 || i >= board.size() || j >= board[0].size() || visited[i][j]) return;
visited[i][j] = true;
if (board[i][j] == 'M') {
board[i][j] = 'X';
return;
}
if (board[i][j] == 'E') {
int c = hasAdjacentMine(board, i, j);
if (c == 0) {
board[i][j] = 'B';
for (int k=0; k<8; k++) {
dfs(board, visited, i+dx[k], j+dy[k]);
}
}
else {
board[i][j] = c + '0';
return;
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
dfs(board, visited, click[0], click[1]);
return board;
}
};
3.2 Minesweeper Java
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
reveal(board, click[0], click[1]);
return board;
}
private void reveal(char[][] board, int i, int j) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'E')
return;
board[i][j] = '0';
int[][] neighbors = {{i-1, j-1}, {i-1, j}, {i-1, j+1},
{i, j-1}, {i, j+1},
{i+1, j-1}, {i+1, j}, {i+1, j+1}};
for (int[] neighbor : neighbors) {
if (neighbor[0] < 0 || neighbor[1] < 0 || neighbor[0] >= board.length || neighbor[1] >= board[0].length)
continue;
if (board[neighbor[0]][neighbor[1]] == 'M')
board[i][j] ++;
}
if (board[i][j] != '0')
return;
board[i][j] = 'B';
for (int[] neighbor : neighbors)
reveal(board, neighbor[0], neighbor[1]);
}
}
3.3 Minesweeper JavaScript
var updateBoard = function(board, click) {
const rows = board.length;
const cols = board[0].length;
dfs(click[0], click[1]);
return board;
function dfs(i, j) {
if (!board[i][j]) return;
if (board[i][j] === 'M') {
board[i][j] = 'X';
return;
}
if (board[i][j] !== 'E') return;
const mines = checkForMine(i, j);
if (mines) {
board[i][j] = mines.toString();
return;
} else {
board[i][j] = 'B';
for (let x = Math.max(i - 1, 0); x < Math.min(i + 2, rows); x++) {
for (let y = Math.max(j - 1, 0); y < Math.min(j + 2, cols); y++) {
dfs(x, y);
}
}
}
}
function checkForMine(x, y) {
let mines = 0;
for (let i = Math.max(x - 1, 0); i < Math.min(x + 2, rows); i++) {
for (let j = Math.max(y - 1, 0); j < Math.min(y + 2, cols); j++) {
if (board[i][j] === 'M') mines++;
}
}
return mines;
}
}
3.4 Minesweeper Python
class Solution(object):
def updateBoard(self, board, click):
def adjacent_mines(i, j):
mines = 0
for x, y in directions:
if 0 <= i + x < M and 0 <= j + y < N and board[i + x][j + y] == "M":
mines += 1
return mines
def dfs(i, j):
mines = adjacent_mines(i, j)
if mines:
board[i][j] = str(mines)
return board
board[i][j] = "B"
for x, y in directions:
if 0 <= i + x < M and 0 <= j + y < N and board[i + x][j + y] == "E":
dfs(i + x, j + y)
return board
if not board: return board
M = len(board)
N = len(board[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0), (1,1), (1,-1), (-1,1), (-1,-1)]
if board[click[0]][click[1]] == "M":
board[click[0]][click[1]] = "X"
return board
if board[click[0]][click[1]] == "E":
return dfs(click[0], click[1])
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(M * N) | O(M * N) |
| Java | O(M * N) | O(M * N) |
| JavaScript | O(M * N) | O(M * N) |
| Python | O(M * N) | O(M * N) |
- All implementations use DFS to explore the grid.
- The C++ implementation uses an explicit
visitedmatrix, which slightly increases memory usage compared to other languages. - The Java, JavaScript, and Python implementations rely on the state of the board itself to track visited cells, avoiding the need for an additional
visitedmatrix. - The time complexity is the same across all implementations because they all potentially visit every cell in the grid once.