1. Minesweeper (LeetCode)
Model answer
The task
Update a Minesweeper board after a cell is clicked. A clicked mine ends the game; an empty cell reveals either its adjacent mine count or, when there are none, the connected empty area and its bordering counts.
Key idea
Use breadth-first search to reveal empty cells. Count neighboring mines before revealing each cell, and only expand from cells with no adjacent mines.
Approach
- If the clicked cell contains a mine, change it to
Xand return. - Otherwise, start a queue with the clicked cell.
- For each queued unrevealed cell, count mines in its eight neighbors.
- Reveal the cell as a digit if the count is positive; otherwise reveal it as
Band enqueue its unrevealed neighbors. - Return the updated board.
from collections import deque
from typing import List
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
rows, cols = len(board), len(board[0])
start_row, start_col = click
if board[start_row][start_col] == "M":
board[start_row][start_col] = "X"
return board
queue = deque([(start_row, start_col)])
directions = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1),
]
while queue:
row, col = queue.popleft()
# A cell may be queued by more than one neighboring blank.
if board[row][col] != "E":
continue
neighbors = []
mine_count = 0
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols:
neighbors.append((nr, nc))
if board[nr][nc] == "M":
mine_count += 1
if mine_count:
board[row][col] = str(mine_count)
else:
board[row][col] = "B"
for nr, nc in neighbors:
if board[nr][nc] == "E":
queue.append((nr, nc))
return board
Complexity:
- Time: O(R × C), since each cell is revealed at most once.
- Space: O(R × C) in the worst case for the BFS queue.
Common follow-ups
- How would you avoid recursion depth issues? Use an iterative queue or stack, as above.
- What if diagonal neighbors do not count? Check only the four orthogonal directions.
- What if the board is too large for memory? Process it in regions or store only changed cells, depending on how the board is represented.