LeetCode 529: Minesweeper

Problem Restatement

We are given a Minesweeper board and a clicked cell.

Each cell can contain one of these characters:

Character	Meaning
`"M"`	An unrevealed mine
`"E"`	An unrevealed empty square
`"B"`	A revealed blank square with no adjacent mines
`"1"` to `"8"`	A revealed square showing the number of adjacent mines
`"X"`	A revealed mine

After the click, we must update the board according to the Minesweeper rules.

If the clicked cell is a mine, change it to "X".

If the clicked cell is an empty square, count its adjacent mines. Adjacent means all 8 neighboring directions: up, down, left, right, and diagonals.

If the empty square has at least one adjacent mine, change it to the digit count.

If the empty square has no adjacent mines, change it to "B" and recursively reveal all adjacent unrevealed empty squares.

Return the updated board.

Input and Output

Item	Meaning
Input	A 2D board and a clicked position
Output	The updated board
Board cell types	`"M"`, `"E"`, `"B"`, `"1"` to `"8"`, `"X"`
Click format	`[row, col]`
Adjacency	8 directions, including diagonals

Function shape:

def updateBoard(board: list[list[str]], click: list[int]) -> list[list[str]]:
    ...

Examples

Consider this board:

board = [
    ["E", "E", "E", "E", "E"],
    ["E", "E", "M", "E", "E"],
    ["E", "E", "E", "E", "E"],
    ["E", "E", "E", "E", "E"],
]
click = [3, 0]

The clicked cell is an unrevealed empty square.

There are no adjacent mines around [3, 0], so it becomes "B".

Then its neighboring empty squares are revealed recursively.

The final board is:

[
    ["B", "1", "E", "1", "B"],
    ["B", "1", "M", "1", "B"],
    ["B", "1", "1", "1", "B"],
    ["B", "B", "B", "B", "B"],
]

Now if we click the mine:

click = [1, 2]

then the mine becomes "X":

[
    ["B", "1", "E", "1", "B"],
    ["B", "1", "X", "1", "B"],
    ["B", "1", "1", "1", "B"],
    ["B", "B", "B", "B", "B"],
]

First Thought: Simulate the Rules Directly

This problem does not require finding a shortest path or optimizing a score.

It asks us to simulate exactly what happens after one click.

The only tricky part is the recursive reveal rule.

When an empty square has no adjacent mines, the reveal spreads to its neighbors. Those neighbors may also have no adjacent mines, so the reveal can keep spreading.

This is a flood-fill problem on a grid.

DFS is a natural fit.

Key Insight

For any clicked empty cell, there are two cases.

First, if it has adjacent mines, we reveal only this cell as a number and stop.

Second, if it has no adjacent mines, we reveal it as "B" and continue exploring its unrevealed empty neighbors.

So the DFS should not always expand. It expands only when the current cell has zero adjacent mines.

This rule is important.

A numbered cell is revealed, but its neighbors are not automatically revealed from that cell.

Algorithm

Use the 8 directions:

directions = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1),
]

Start from the clicked cell.

If it is "M", change it to "X" and return the board.

Otherwise, run DFS on the clicked cell.

For each DFS call at position (row, col):

Count adjacent mines.
If the count is greater than 0, change the cell to that digit and stop.
If the count is 0, change the cell to "B".
Recursively reveal all adjacent cells that are still "E".

We only recurse into "E" cells. This avoids revisiting already revealed cells.

Correctness

If the clicked cell is a mine, the algorithm changes it to "X" and returns immediately. This matches the game rule for revealing a mine.

Now consider a clicked empty square. The algorithm counts all mines in the 8 adjacent cells. If the count is positive, it writes that count into the current cell and does not recurse. This matches the rule that an empty square adjacent to at least one mine becomes a digit and no further squares are revealed from it.

If the count is zero, the algorithm changes the current cell to "B" and recursively processes every adjacent unrevealed empty square. This matches the rule that a blank square causes all adjacent unrevealed squares to be revealed recursively.

The algorithm only recurses into cells marked "E". Once a cell is changed to "B" or a digit, it will not be processed again. Therefore, the recursion terminates.

Every cell revealed by the Minesweeper rule is reached by this recursive process, because each reveal step follows an adjacency edge from a blank square. Every cell processed by the algorithm is also allowed by the rule, because recursion only happens from cells with zero adjacent mines.

Therefore, the returned board is exactly the board after applying the click rules.

Complexity

Let:

m = number of rows
n = number of columns

Metric	Value	Why
Time	`O(m * n)`	Each cell can be revealed at most once
Space	`O(m * n)`	The recursion stack can contain many cells in the worst case

For each revealed cell, we check at most 8 neighbors, which is constant work.

Implementation

class Solution:
    def updateBoard(self, board: list[list[str]], click: list[int]) -> list[list[str]]:
        rows = len(board)
        cols = len(board[0])

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        def count_adjacent_mines(row: int, col: int) -> int:
            count = 0

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "M":
                    count += 1

            return count

        def dfs(row: int, col: int) -> None:
            mine_count = count_adjacent_mines(row, col)

            if mine_count > 0:
                board[row][col] = str(mine_count)
                return

            board[row][col] = "B"

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "E":
                    dfs(nr, nc)

        row, col = click

        if board[row][col] == "M":
            board[row][col] = "X"
            return board

        dfs(row, col)
        return board

Code Explanation

We first store the board dimensions:

rows = len(board)
cols = len(board[0])

The directions array contains all 8 neighboring moves.

directions = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1),
]

The helper count_adjacent_mines checks every neighbor and counts mines:

if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "M":
    count += 1

We only count unrevealed mines "M".

Inside dfs, we first count adjacent mines:

mine_count = count_adjacent_mines(row, col)

If there is at least one adjacent mine, we write the digit and stop:

if mine_count > 0:
    board[row][col] = str(mine_count)
    return

If there are no adjacent mines, the square becomes blank:

board[row][col] = "B"

Then we reveal adjacent unrevealed empty squares:

if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "E":
    dfs(nr, nc)

This condition also prevents repeated visits, because a visited empty cell is changed away from "E".

BFS Version

DFS is concise, but BFS also works and avoids recursion depth issues.

from collections import deque

class Solution:
    def updateBoard(self, board: list[list[str]], click: list[int]) -> list[list[str]]:
        rows = len(board)
        cols = len(board[0])

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        row, col = click

        if board[row][col] == "M":
            board[row][col] = "X"
            return board

        queue = deque([(row, col)])

        while queue:
            row, col = queue.popleft()

            if board[row][col] != "E":
                continue

            mine_count = 0

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "M":
                    mine_count += 1

            if mine_count > 0:
                board[row][col] = str(mine_count)
                continue

            board[row][col] = "B"

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "E":
                    queue.append((nr, nc))

        return board

Testing

def run_tests():
    s = Solution()

    board = [
        ["E", "E", "E", "E", "E"],
        ["E", "E", "M", "E", "E"],
        ["E", "E", "E", "E", "E"],
        ["E", "E", "E", "E", "E"],
    ]

    expected = [
        ["B", "1", "E", "1", "B"],
        ["B", "1", "M", "1", "B"],
        ["B", "1", "1", "1", "B"],
        ["B", "B", "B", "B", "B"],
    ]

    assert s.updateBoard(board, [3, 0]) == expected

    board = [
        ["B", "1", "E", "1", "B"],
        ["B", "1", "M", "1", "B"],
        ["B", "1", "1", "1", "B"],
        ["B", "B", "B", "B", "B"],
    ]

    expected = [
        ["B", "1", "E", "1", "B"],
        ["B", "1", "X", "1", "B"],
        ["B", "1", "1", "1", "B"],
        ["B", "B", "B", "B", "B"],
    ]

    assert s.updateBoard(board, [1, 2]) == expected

    board = [["E"]]
    assert s.updateBoard(board, [0, 0]) == [["B"]]

    board = [["M"]]
    assert s.updateBoard(board, [0, 0]) == [["X"]]

    print("all tests passed")

run_tests()

Test	Why
Large empty reveal	Checks recursive flood fill
Click on mine	Checks game-over rule
Single empty cell	Checks zero-neighbor blank case
Single mine cell	Checks smallest mine case