We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Minesweeper

Number: 529

Difficulty: Medium

Paid? No

Companies: Meta, Uber, Google, Docusign, Yext, Amazon

Problem Description

(A short summary or question text)

The problem simulates the Minesweeper game. Given an m x n board with unrevealed mines ('M') and empty squares ('E'), along with some already revealed cells, you must update the board based on a click position. If the clicked cell is a mine, it becomes 'X'. If the clicked cell is an empty square, you must either reveal it as a digit representing the count of adjacent mines or as a blank ('B') and recursively reveal its neighbors if there are zero adjacent mines.

Key Insights

Use DFS or BFS to reveal multiple cells starting from the clicked cell.
For each cell, count mines in all 8 adjacent directions.
Stop recursion when a cell with adjacent mines is encountered.
Be cautious with board boundaries to avoid index errors.

Space and Time Complexity

Time Complexity: O(m * n) in the worst case when all cells are revealed. Space Complexity: O(m * n) due to recursion stack or queue use.

Solution

A Depth-First Search (DFS) approach is used to recursively reveal cells. When a cell is clicked:

If it is a mine, mark it as 'X' and terminate.
Otherwise, count the adjacent mines.
If the mine count is non-zero, update the cell with this count.
If the mine count is zero, mark the cell as 'B' and recursively reveal all adjacent unrevealed cells. This method handles all edge cases by ensuring that the recursion stops when a cell has at least one adjacent mine.

Code Solutions

# Python solution with DFS
class Solution:
    def updateBoard(self, board, click):
        # Get board dimensions
        rows, cols = len(board), len(board[0])
        
        # Define 8 possible directions (up, down, left, right, and diagonals)
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        
        def dfs(r, c):
            # Check boundary conditions and if cell is an unrevealed empty cell
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'E':
                return
            
            mine_count = 0
            # Count adjacent mines
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'M':
                    mine_count += 1
            
            if mine_count > 0:
                # Update cell with mine count if any adjacent mines are present
                board[r][c] = str(mine_count)
            else:
                # Mark the cell as 'B' and recursively reveal neighbors
                board[r][c] = 'B'
                for dr, dc in directions:
                    dfs(r + dr, c + dc)
        
        click_r, click_c = click
        # If mine is clicked, game over: mark as 'X'
        if board[click_r][click_c] == 'M':
            board[click_r][click_c] = 'X'
        else:
            dfs(click_r, click_c)
        
        return board

← Back to All Questions