Skip to main content
Talentd

Minesweeper - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchMatrix21 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

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:

  1. If a mine 'M' is revealed, then the game is over. You should change it to 'X'.
  2. 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.
  3. 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.
  4. 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.length
  • n == board[i].length
  • 1 <= m, n <= 50
  • board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'.
  • click.length == 2
  • 0 <= clickr < m
  • 0 <= clickc < n
  • board[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.

The C code uses a recursive DFS function that checks each direction from the current cell to find and count adjacent mines. If there are no adjacent mines, it recursively visits neighboring cells.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) - In the worst case, every cell might be visited once.

Space Complexity: O(m * n) - Due to the recursion stack for DFS.

Try this approach in the editor →

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.

This C code uses a queue to implement BFS for revealing squares on the board. A helper function manages the queue operations. Visited squares are marked during processing as '#' to prevent re-exploration. It iteratively processes cells and updates the board.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) - Visiting each cell a limited number of times.

Space Complexity: O(m * n) - The queue might store all cells in the worst case.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS) Approach

Time Complexity: O(m * n) - In the worst case, every cell might be visited once.

Space Complexity: O(m * n) - Due to the recursion stack for DFS.

Breadth-First Search (BFS) Approach

Time Complexity: O(m * n) - Visiting each cell a limited number of times.

Space Complexity: O(m * n) - The queue might store all cells in the worst case.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

LeetCode 529. Minesweeper Explanation and Solution • happygirlzt • 12,118 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minesweeper with our built-in code editor and test cases.

Practice on FleetCode
Previous

Detonate the Maximum Bombs