Minesweeper - Video Solutions
LeetCode 529. Minesweeper Explanation and Solution
Minesweeper - Video Solution
Watch 10 video solutions for Minesweeper, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by happygirlzt has 12,118 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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"]]
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.
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 |