LeetCode 529 - Minesweeper

LeetCode Problem 529

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem asks us to simulate one move in the classic Minesweeper game. We are given a two dimensional grid representing the current game board, along with the coordinates of a user click. Our task is to update the board according to the rules of Minesweeper.

Each cell on the board contains one of several possible values:

• 'M' means the cell contains an unrevealed mine.
• 'E' means the cell is an unrevealed empty square.
• 'B' means the cell has already been revealed and has no adjacent mines.
• '1' through '8' represent revealed cells that show how many adjacent mines exist.
• 'X' represents a mine that was clicked and exploded.

The click is guaranteed to land on either an unrevealed mine 'M' or an unrevealed empty square 'E'.

The rules for updating the board are:

1. If the clicked cell is a mine 'M', the game ends immediately and that cell becomes 'X'.
2. If the clicked cell is an empty square 'E' with at least one adjacent mine, it becomes a digit showing the number of adjacent mines.
3. If the clicked cell is an empty square 'E' with no adjacent mines, it becomes 'B', and all neighboring unrevealed cells are recursively revealed.
4. The recursion continues until every reachable empty region has been processed.

The key detail is the recursive revealing behavior. When a blank square with zero neighboring mines is uncovered, the game automatically expands outward into all neighboring unrevealed cells. This creates a flood fill style traversal over the board.

The board dimensions are at most 50 x 50, meaning there are at most 2500 cells. This is small enough that traversing the entire board is completely feasible. Because each cell only has eight possible neighbors, depth-first search or breadth-first search works very naturally.

Several edge cases are important:

• Clicking directly on a mine must immediately terminate processing.
• A revealed empty cell with adjacent mines should stop expansion.
• Recursive revealing must avoid revisiting cells repeatedly.
• Corner and edge cells have fewer than eight neighbors, so boundary checking is critical.
• The board may already contain revealed cells from previous moves, but the clicked cell is guaranteed to be unrevealed.

Approaches

Brute Force Approach

A naive approach would repeatedly scan the entire board after every reveal operation to determine which cells should change next. For every newly revealed blank square, we could iterate through all cells again and decide whether additional cells should become revealed.

This works because eventually every reachable cell will be processed correctly according to the game rules. However, it is highly inefficient because the same cells are examined many times unnecessarily.

For example, after revealing one blank square, we may rescan the entire board to find neighboring cells to reveal. Then after revealing those neighbors, we scan the entire board again. This repeated global processing wastes computation.

Although the board size is not enormous, this approach scales poorly and is conceptually cumbersome.

Optimal Approach, DFS or BFS Flood Fill

The key insight is that revealing empty regions behaves exactly like a graph traversal problem.

Whenever we reveal a blank square with zero adjacent mines, we must recursively reveal all neighboring unrevealed cells. This is essentially a flood fill over the board.

Instead of rescanning the entire grid repeatedly, we only visit cells that are actually reachable from the clicked position.

The process is:

• Start from the clicked cell.
• Count adjacent mines.
• If mines exist, place the digit and stop.
• Otherwise mark the cell as 'B' and recursively explore all neighbors.

Each cell is processed at most once, making the traversal efficient.

Depth-first search and breadth-first search are both valid. DFS is slightly simpler to implement recursively, while BFS avoids recursion depth concerns. Given the small constraint size, recursive DFS is perfectly safe here.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((mn)^2)	O(1)	Repeatedly scans the whole board after each reveal
Optimal DFS/BFS	O(mn)	O(mn)	Visits each cell at most once using flood fill

Algorithm Walkthrough

1. Read the clicked coordinates from the click array.
2. If the clicked cell contains a mine 'M', immediately change it to 'X' and return the board. This represents the game ending after clicking a mine.
3. Otherwise, begin a DFS traversal from the clicked cell.
4. For the current cell, count how many adjacent cells contain mines. There are eight possible neighboring directions:

• up
• down
• left
• right
• four diagonals

5. If the adjacent mine count is greater than zero, convert the current cell into the corresponding digit character and stop recursion from this cell. We do not continue expanding because Minesweeper only auto-expands from cells with zero adjacent mines.
6. If the adjacent mine count is zero:

• Mark the current cell as 'B'.
• Recursively visit all neighboring unrevealed cells 'E'.

7. Before recursively exploring a neighbor:

• Ensure the coordinates are inside the board boundaries.
• Ensure the neighbor is still unrevealed 'E'.

This prevents infinite recursion and repeated processing. 8. Continue the traversal until all reachable blank regions have been processed. 9. Return the updated board.

Why it works

The algorithm maintains the invariant that every processed cell exactly matches Minesweeper rules.

• If a cell has adjacent mines, it becomes the correct digit and expansion stops.
• If a cell has no adjacent mines, it becomes 'B' and recursively reveals all neighboring unrevealed cells.
• Every unrevealed cell is visited at most once.

Because DFS explores precisely the connected component of safe blank cells reachable from the click, the final board state is exactly the same as the actual Minesweeper game behavior.

Python Solution

from typing import List

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 dfs(row: int, col: int) -> None:
            if board[row][col] != 'E':
                return

            mine_count = 0

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

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

            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:
                    dfs(nr, nc)

        click_row, click_col = click

        if board[click_row][click_col] == 'M':
            board[click_row][click_col] = 'X'
            return board

        dfs(click_row, click_col)

        return board

The implementation begins by storing the board dimensions and defining the eight possible movement directions. These directions are reused both for counting adjacent mines and for recursive exploration.

The dfs helper function performs the recursive reveal operation. The first check ensures we only process unrevealed empty cells 'E'. This prevents revisiting cells and avoids infinite recursion.

Next, the function counts adjacent mines by iterating through all eight neighboring positions. Boundary checks ensure we do not access invalid coordinates.

If one or more mines are adjacent, the cell becomes the corresponding digit character. Recursion stops because Minesweeper only expands through zero-mine cells.

If no neighboring mines exist, the cell becomes 'B', and DFS recursively explores all neighboring cells.

Finally, the main function handles the special case where the clicked cell is a mine. Otherwise, it starts DFS from the clicked location and returns the updated board.

Go Solution

func updateBoard(board [][]byte, click []int) [][]byte {
    rows := len(board)
    cols := len(board[0])

    directions := [][2]int{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1},  {1, 0},  {1, 1},
    }

    var dfs func(int, int)

    dfs = func(row int, col int) {
        if board[row][col] != 'E' {
            return
        }

        mineCount := 0

        for _, dir := range directions {
            nr := row + dir[0]
            nc := col + dir[1]

            if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
                if board[nr][nc] == 'M' {
                    mineCount++
                }
            }
        }

        if mineCount > 0 {
            board[row][col] = byte('0' + mineCount)
            return
        }

        board[row][col] = 'B'

        for _, dir := range directions {
            nr := row + dir[0]
            nc := col + dir[1]

            if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
                dfs(nr, nc)
            }
        }
    }

    r := click[0]
    c := click[1]

    if board[r][c] == 'M' {
        board[r][c] = 'X'
        return board
    }

    dfs(r, c)

    return board
}

The Go implementation closely mirrors the Python version. The board uses [][]byte instead of strings because Go commonly represents character grids with bytes for efficiency.

One notable difference is digit conversion. In Go, we construct digit characters using:

byte('0' + mineCount)

This converts an integer count into its ASCII digit representation.

The recursive DFS logic and boundary handling are otherwise identical.

Worked Examples

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]

The click lands on (3,0).

Initial DFS begins at (3,0).

Cell	Adjacent Mines	Result
(3,0)	0	Becomes 'B'
(2,0)	0	Becomes 'B'
(1,0)	0	Becomes 'B'
(0,0)	0	Becomes 'B'
(0,1)	1	Becomes '1'

Expansion continues outward through all connected zero-mine regions.

Eventually the board becomes:

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

The mine itself remains unrevealed because it was not clicked.

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]

The clicked position (1,2) contains 'M'.

According to the rules:

• Change 'M' to 'X'
• Return immediately

Final board:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(mn)	Each cell is visited at most once
Space	O(mn)	Recursive DFS stack can contain many cells

The DFS traversal processes each board position at most once because cells change from 'E' into either 'B' or a digit after processing. Since no processed cell is revisited, the total work is linear in the number of cells.

The recursion stack may grow as large as the number of reachable cells in the worst case, such as a board with no mines.

Test Cases

from typing import List

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 dfs(row: int, col: int) -> None:
            if board[row][col] != 'E':
                return

            mine_count = 0

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

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

            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:
                    dfs(nr, nc)

        r, c = click

        if board[r][c] == 'M':
            board[r][c] = 'X'
            return board

        dfs(r, c)

        return board

sol = Solution()

# Example 1
board1 = [
    ["E","E","E","E","E"],
    ["E","E","M","E","E"],
    ["E","E","E","E","E"],
    ["E","E","E","E","E"]
]

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

assert sol.updateBoard(board1, [3,0]) == expected1  # flood fill expansion

# Example 2
board2 = [
    ["B","1","E","1","B"],
    ["B","1","M","1","B"],
    ["B","1","1","1","B"],
    ["B","B","B","B","B"]
]

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

assert sol.updateBoard(board2, [1,2]) == expected2  # clicking a mine

# Single empty cell
board3 = [["E"]]
expected3 = [["B"]]

assert sol.updateBoard(board3, [0,0]) == expected3  # smallest empty board

# Single mine cell
board4 = [["M"]]
expected4 = [["X"]]

assert sol.updateBoard(board4, [0,0]) == expected4  # smallest mine board

# Adjacent mine count
board5 = [
    ["E","M"],
    ["E","E"]
]

expected5 = [
    ["1","M"],
    ["E","E"]
]

assert sol.updateBoard(board5, [0,0]) == expected5  # reveals digit only

# Large blank expansion
board6 = [
    ["E","E","E"],
    ["E","E","E"],
    ["E","E","E"]
]

expected6 = [
    ["B","B","B"],
    ["B","B","B"],
    ["B","B","B"]
]

assert sol.updateBoard(board6, [1,1]) == expected6  # full board flood fill

Test	Why
Example 1	Validates recursive flood fill behavior
Example 2	Validates clicking directly on a mine
Single empty cell	Tests smallest possible non-mine board
Single mine cell	Tests smallest possible mine board
Adjacent mine count	Ensures digit generation works correctly
Large blank expansion	Tests full recursive traversal across board

Edge Cases

One important edge case occurs when the clicked cell is a mine. This case is easy to mishandle if the DFS logic starts immediately without checking the clicked value first. The implementation handles this by checking for 'M' before recursion begins and converting it directly to 'X'.

Another important case is when an empty cell has adjacent mines. In this situation, the cell should become a digit and recursion must stop immediately. A buggy implementation might continue expanding neighbors incorrectly. The solution avoids this by returning immediately after assigning the digit.

A third critical edge case involves boundary cells, especially corners. These cells do not have all eight neighbors. Without careful boundary checks, the algorithm could access invalid indices and crash. Every neighbor access is guarded with range checks to ensure coordinates stay inside the board.

A fourth subtle case involves revisiting cells during recursion. Since neighboring cells recursively explore one another, failing to mark visited cells properly could cause infinite recursion. The implementation prevents this by only processing cells whose value is exactly 'E'. Once a cell changes to 'B' or a digit, it cannot be revisited.