529. Minesweeper

Minesweeper is a deceptively rich problem. On the surface, it looks like a grid manipulation task. In reality, it tests your understanding of graph traversal, boundary handling, recursion vs iteration, and state transitions.

Interviewers like this problem because it mirrors real-world systems: one action can trigger a cascade of updates, and your job is to propagate changes correctly, efficiently, and safely.

Problem statement

You are given an m x n board representing a Minesweeper game, where:

• ‘M’ represents an unrevealed mine
• ‘E’ represents an unrevealed empty cell
• ‘B’ represents a revealed blank cell with no adjacent mines
• ‘1’ to ‘8’ represent revealed cells with that many adjacent mines
• ‘X’ represents a revealed mine

You are also given a click position [row, col].

Update the board according to the following rules:

• If a mine (‘M’) is clicked, it becomes ‘X’ and the game ends.
• If an empty cell (‘E’) is clicked:
  • Count adjacent mines.
  • If the count is greater than 0, reveal the cell with that number.
  • If the count is 0, reveal it as ‘B’ and recursively reveal all adjacent unrevealed empty cells.

Return the updated board after the click position.

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’.

Examples

Intuition

Minesweeper is best understood as a problem of controlled reveal propagation. When a user clicks a cell, the result is not always limited to that cell alone. In some cases, only a single cell is revealed. In others, the reveal spreads outward until a stopping condition is reached.

This spreading behavior immediately hints at a traversal-based solution. However, unlike a classic flood fill where all connected regions are revealed, Minesweeper introduces an important constraint: expansion only continues when the current cell has zero adjacent mines. The moment a cell is found to be adjacent to one or more mines, the reveal stops at that cell.

Because of this rule, the problem is not just about traversing the board, but about making a decision at every step whether to stop or continue based on local information. Additionally, each cell must be processed exactly once to avoid infinite loops or repeated work.

DFS-based flood fill approach

We solve this problem using Depth First Search (DFS), treating the board as a graph.

Each cell can be viewed as a node with up to eight neighboring nodes (horizontal, vertical, and diagonal).

Clicking a cell may trigger a recursive reveal depending on its surroundings. DFS is well-suited here because it naturally explores all reachable cells from the click position while allowing us to stop expansion as soon as a boundary condition is met.

At a high level, the algorithm performs the following actions repeatedly:

• Count how many adjacent cells contain mines.
• If the count is non-zero, reveal the cell with that number and stop.
• If the count is zero, reveal the cell as blank and recursively process its neighbors.

By structuring the solution this way, we guarantee correctness while keeping the implementation simple and efficient. The DFS continues only where the game rules allow it to, and the board itself acts as the visited state.

Step-by-step algorithm

1. Read the click position (r, c) from the input.
2. If board[r][c] == ‘M’:
   1. The user has clicked directly on a mine.
   2. Change the cell value to ‘X’ to indicate a revealed mine.
   3. Return the board immediately since the game ends.
3. Define the 8 possible directions representing all adjacent cells:
   1. Horizontal, vertical, and diagonal neighbors.
4. Define a DFS function dfs(x, y) that reveals cells starting from position (x, y):
   1. Initialize mine_count = 0 to count how many adjacent mines surround the current cell.
   2. For each of the 8 directions:
      1. Compute the neighboring cell (nx, ny).
      2. Check that (nx, ny) lies within the board boundaries.
      3. If the neighboring cell contains a mine (‘M’), increment mine_count.
   3. After checking all neighbors:
      1. If mine_count > 0:
         1. Update board[x][y] with the string value of mine_count.
         2. Stop further expansion from this cell, since numbered cells do not propagate.
   4. If mine_count == 0:
      1. Update board[x][y] to ‘B’, indicating a blank revealed cell.
      2. For each of the 8 directions again:
         1. Compute the neighboring cell (nx, ny).
         2. Ensure (nx, ny) is inside the board.
         3. If the neighboring cell is still unrevealed (‘E’):
            1. Recursively call dfs(nx, ny) to continue the reveal process.
5. Start the reveal process by calling dfs(r, c) on the clicked cell.
6. Once all reachable cells have been processed, return the updated board.

Code implementation

Let’s look at the code for this solution below:

def updateBoard(board, click):
    rows, cols = len(board), len(board[0])
    r, c = click

    # If a mine is clicked, reveal it and end the game
    if board[r][c] == 'M':
        board[r][c] = 'X'
        return board

    # All 8 possible directions (including diagonals)
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1)
    ]

    def dfs(x, y):
        mine_count = 0

        # Count adjacent mines
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                if board[nx][ny] == 'M':
                    mine_count += 1

        # If there are adjacent mines, reveal count and stop
        if mine_count > 0:
            board[x][y] = str(mine_count)
            return

        # Otherwise, reveal as blank
        board[x][y] = 'B'

        # Recursively reveal adjacent empty cells
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                if board[nx][ny] == 'E':
                    dfs(nx, ny)

    # Start DFS from the clicked cell
    dfs(r, c)
    return board

# Helper function for printing the board (not part of actual algorithm)
def printBoard(board):
    rows, cols = len(board), len(board[0])

    horizontal_border = "\t\t+" + "---+" * cols
    print(horizontal_border)

    for row in board:
        print("\t\t| " + " | ".join(row) + " |")
        print(horizontal_border)

    print()


def main():
    testCases = [
        (
            [
                ['E', 'E', 'E', 'E', 'E'],
                ['E', 'E', 'M', 'E', 'E'],
                ['E', 'E', 'E', 'E', 'E'],
                ['E', 'E', 'E', 'E', 'E']
            ],
            [3, 0]
        )
    ]

    for i, (board, click) in enumerate(testCases, 1):
        print(f"{i}.\t Input board:")
        printBoard(board)

        print(f"\t Click position: {click}")
        updated = updateBoard(board, click)

        print("\t Updated board:")
        printBoard(updated)
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of the solution is O(m × n) in the worst case, where m is the number of rows and n is the number of columns in the board.

Although the DFS may branch in multiple directions, each cell is processed at most once. As soon as a cell is revealed, its value is updated from ‘E’ to either ‘B’ or a digit, which prevents it from being revisited.

For every processed cell, we examine up to 8 neighbors, which is a constant-time operation. As a result, the total work scales linearly with the number of cells in the board.

Space complexity

The space complexity of the algorithm is O(m × n) in the worst case.

The primary space usage comes from the recursion stack in DFS. In the worst-case scenario such as a board with no mines where all cells are revealed the recursion may go as deep as the total number of cells.

Apart from the recursion stack, no additional data structures are used. The board itself serves as the visited state by being updated in place.

Common pitfalls and interview tips

One common mistake is delaying the board update until after recursion. This leads to repeated visits and, in some cases, infinite loops.

Another frequent error is expanding even when adjacent mines exist.

From an interview perspective, it is valuable to mention that DFS and BFS are interchangeable here. DFS is simpler to code, while BFS is safer for very large boards.