How do you solve Minesweeper on LeetCode?

Minesweeper (LeetCode #529) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding the recursive nature of the problem is crucial.

What is the brute force solution for Minesweeper?

The brute force approach for Minesweeper is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking the clicked cell and revealing it based on its type. If it's an empty square, we recursively reveal its neighbors until we hit squares with adjacent mines or mines themselves. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Minesweeper?

Minesweeper uses the following concepts: Array, Depth-First Search, Breadth-First Search, Matrix. The recommended patterns to study are: Depth-First Search, Recursion.

What are the interview tips for Minesweeper?

Explain your thought process clearly while coding. Ask clarifying questions about the problem constraints. Practice writing clean and efficient code.

What are common mistakes when solving Minesweeper?

Not handling edge cases like clicking on the border of the board. Failing to check all adjacent cells correctly.

#529

Minesweeper

Medium

ArrayDepth-First SearchBreadth-First SearchMatrixDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a depth-first search (DFS) approach to reveal cells efficiently. By leveraging recursion, we can explore all adjacent cells without redundant checks, making it faster than the brute force approach.

⚙️

Algorithm

3 steps

1Step 1: If the clicked cell is a mine, change it to 'X' and return.
2Step 2: If it's an empty cell, count adjacent mines. If there are none, change it to 'B' and recursively reveal adjacent cells.
3Step 3: If there are adjacent mines, change the cell to the count.

solution.py24 lines

1def updateBoard(board, click):
2    rows, cols = len(board), len(board[0])
3    r, c = click
4    if board[r][c] == 'M':
5        board[r][c] = 'X'
6    else:
7        def countMines(r, c):
8            directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
9            count = 0
10            for dr, dc in directions:
11                nr, nc = r + dr, c + dc
12                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'M':
13                    count += 1
14            return count
15        mine_count = countMines(r, c)
16        if mine_count > 0:
17            board[r][c] = str(mine_count)
18        else:
19            board[r][c] = 'B'
20            for dr, dc in directions:
21                nr, nc = r + dr, c + dc
22                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'E':
23                    updateBoard(board, [nr, nc])
24    return board

ℹ

Complexity note: The time complexity is O(n) because we explore each cell once, while the space complexity is O(n) due to the recursion stack in the worst case.

1Understanding the recursive nature of the problem is crucial.
2Counting adjacent mines efficiently can significantly optimize the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.