Domain 2MediumCORE

Minesweeper

We are given a 2D grid representing a Minesweeper board where cells can be unrevealed empty squares ('E'), unrevealed mines ('M'), blank safe squares ('B'), or digits indicating adjacent mine counts. We receive a specific click coordinate [row, col]. Our goal is to simulate the reveal logic for that single cell and propagate changes according to Minesweeper rules until no more cells can be revealed by this action.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search

529. Minesweeper

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 61.5%


Problem Breakdown

We are given a 2D grid representing a Minesweeper board where cells can be unrevealed empty squares (‘E’), unrevealed mines (‘M’), blank safe squares (‘B’), or digits indicating adjacent mine counts. We receive a specific click coordinate [row, col]. Our goal is to simulate the reveal logic for that single cell and propagate changes according to Minesweeper rules until no more cells can be revealed by this action.

Inputs:

  • board: A 2D list of characters (char[][]).
  • click: A list [row, col] representing the clicked position (guaranteed to be ‘M’ or ‘E’).

Outputs:

  • The modified board. If a mine is revealed (‘X’), we stop. If an empty square has adjacent mines, it becomes a digit and stops recursion for that branch. If an empty square has zero adjacent mines, it becomes ‘B’, triggering recursive reveals of its neighbors.

Constraints & Edge Cases:

  • Board dimensions are small (up to 50x50).
  • Click is guaranteed valid (‘M’ or ‘E’).
  • We must handle boundary checks when accessing neighbor coordinates.
  • If the clicked cell is a mine, we change it immediately and return without further recursion.

Intuition

A naive approach might be to iterate through every cell on the board to check if it needs revealing based on some global state, but that ignores the causal link between cells (revealing one ‘B’ triggers neighbors). The core mechanic here is propagation. When we click a safe square (‘E’) with no adjacent mines, we are essentially performing a flood fill.

If I simply change board[r][c] to its state and stop, I miss the requirement that unrevealed squares must be revealed recursively if they connect via ‘B’ cells. This suggests a graph traversal problem where nodes are grid coordinates. Since the order of visiting neighbors doesn’t matter for correctness (unlike topological sort), either Breadth-First Search (BFS) or Depth-First Search (DFS) works. DFS is often more concise to implement in Python using recursion, avoiding explicit queue management overhead.

The key insight: We only need to traverse the connected component of ‘E’ cells reachable from the click that are safe (‘0 mines adjacent’). Any cell with > 0 adjacent mines acts as a barrier for further recursive propagation (it gets revealed but doesn’t trigger neighbors).

Approach

  1. Handle Immediate Game Over: Check if board[click_r][click_c] is ‘M’. If so, change to ‘X’ and return immediately. No recursion needed.
  2. Define Neighbor Logic: Create a helper function or loop that iterates over the 8 surrounding directions (horizontal, vertical, diagonal). We need boundary checks for every neighbor access.
  3. Count Adjacent Mines: For any cell we visit during traversal, count how many neighbors are currently ‘M’. Note: Only unrevealed mines (‘M’) contribute to this count; revealed squares or digits do not change the mine status of a square (though they won’t be visited as targets anyway).
  4. Update State & Decide Recursion:
    • If mine_count > 0: Update cell with digit string (str(mine_count)). Do NOT recurse further from this branch because neighbors are not triggered by the “safe” rule here. Return/Stop for this path.
    • If mine_count == 0: Update cell to ‘B’. Then, iterate through all valid neighbor coordinates and recursively call the reveal function on them (if they haven’t been revealed yet).
  5. Termination: The recursion naturally terminates when we hit board boundaries or cells that are already not ‘E’ (either digits, mines, blank squares from previous steps, or game-over states).

Complexity Analysis

  • Time Complexity: O(Row * Col). In the worst case where every cell is revealed (‘B’), each cell in the grid is visited a constant number of times. Counting neighbors takes O(1) (8 directions). Thus, total time scales linearly with board size N*M.
  • Space Complexity: O(Row * Col) for recursion stack depth. In the worst-case scenario where we have to traverse every cell in a snake-like pattern before hitting boundaries or mines, the call stack could grow proportional to the number of cells (though practically limited by grid geometry). Given constraints [1, 50], this is well within Python’s default recursion limit (~1000 frames), but technically O(N*M) space.

Solution

from typing import List

def updateBoard(board: List[List[str]], click: List[int]) -> List[List[str]]:
    rows = len(board)
    cols = len(board[0])
    
    # Directions for 8 neighbors (horizontal, vertical, diagonal)
    directions = [(-1,-1), (-1,0), (-1,1), 
                  (0,-1),           (0,1), 
                  (1,-1),   (1,0),  (1,1)]

    def count_mines(r: int, c: int) -> int:
        """Counts adjacent mines ('M') around the given cell."""
        mine_count = 0
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check boundaries and if neighbor is an unrevealed mine
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'M':
                mine_count += 1
        return mine_count

    def reveal(r: int, c: int):
        """Recursively reveals cells starting from (r,c)."""
        
        # Base case: If cell is not unrevealed ('E'), stop. 
        # We only process 'M' or 'E', but if it's already revealed we skip.
        if board[r][c] != 'E':
            return

        mine_count = count_mines(r, c)
        
        if mine_count > 0:
            # If adjacent mines exist, reveal as digit and stop recursion for this branch
            board[r][c] = str(mine_count)
        else:
            # No adjacent mines -> Blank square ('B')
            board[r][c] = 'B'
            
            # Recursively process all unrevealed neighbors (flood fill logic)
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    reveal(nr, nc)

    row_click, col_click = click
    
    # Handle the specific case of clicking a mine immediately (Game Over)
    if board[row_click][col_click] == 'M':
        board[row_click][col_click] = 'X'
        
    else:
        # Clicked an empty square ('E'), start reveal logic
        reveal(row_click, col_click)

    return board

Edge Cases Handled

  • Clicking a Mine: The code explicitly checks if the clicked cell is ‘M’. If so, it changes to ‘X’ and returns immediately without triggering recursion. This prevents infinite loops or invalid state updates on game-over scenarios.
  • Boundary Conditions: Every neighbor access (nr, nc) includes boundary checks (0 <= nr < rows etc.) before accessing the board array, preventing index out of range errors at edges/corners.
  • Already Revealed Cells: The recursive function starts with a check if board[r][c] != 'E': return. This ensures we don’t process cells that have already been updated to digits (‘1’-‘8’), blanks (‘B’), or revealed mines (‘X’) during the traversal, preventing redundant work.
  • Single Cell Board: The logic holds for 1x1 grids; neighbor loops simply won’t execute valid indices, and boundary checks handle it gracefully.