#529

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Minesweeper

Solve the Minesweeper game by updating revealed squares and handling clicks with Depth-First Search and Array manipulation.

array depth first search breadth first search matrix

Problem Statement

In the Minesweeper game, you are provided with a grid representing a game board. Each cell in the grid can be either an empty square ('E'), a mine ('M'), or a number representing the count of adjacent mines ('1'-'8'). Your task is to process the result of a click on a specific cell. If a mine is clicked, the game ends. If an empty square is clicked, you need to reveal that square, and if it has any adjacent mines, display the number of mines in that square.

You are given a 2D array representing the board and an integer array specifying the click's coordinates. You must update the board to reflect the new game state, revealing cells and adjacent mine counts where necessary. Continue updating the board until there are no further empty cells to reveal, following the rules of Minesweeper.

Examples

Example 1

Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]

Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

Example details omitted.

Example 2

Input: board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]

Output: [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

Example details omitted.

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

Solution Approach

Depth-First Search

The primary approach to solving this problem is using Depth-First Search (DFS). Starting from the clicked cell, if the cell is an empty square, reveal it and recursively check its adjacent cells. If any of the adjacent cells are empty squares themselves, expand the search until all reachable empty squares are revealed.

Array Traversal and Updates

You'll need to manipulate the board using Array indexing. After a click, check the state of the clicked cell. If it's an empty square, the adjacent cells must be checked to calculate the number of surrounding mines, which will be displayed. This requires careful handling of array bounds during the traversal process.

Handling Edge Cases

Consider edge cases where the click is on a corner or the board has a large number of mines close together. Proper boundary checks and recursive DFS implementation are essential to ensure that no out-of-bounds errors occur and all cells are updated correctly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the DFS traversal. In the worst case, you may need to visit all cells, which results in O(m * n) time, where m and n are the dimensions of the board. The space complexity is O(m * n) due to the recursion stack used in DFS and the storage required for the board itself.

What Interviewers Usually Probe

Look for efficient DFS implementation that minimizes unnecessary checks.
Ensure the candidate handles edge cases like clicks on borders and corners.
Check if they can correctly update adjacent cells while respecting the grid's boundaries.

Common Pitfalls or Variants

Common pitfalls

Not handling recursion depth properly, leading to stack overflow or missing updates.
Incorrect boundary checks when accessing neighboring cells, leading to out-of-bounds errors.
Failing to efficiently calculate adjacent mines, resulting in incorrect board updates.

Follow-up variants

Modify the board size to handle larger or smaller grids efficiently.
Introduce additional game features like flags or different mine types.
Optimize the algorithm to use Breadth-First Search (BFS) instead of DFS.

FAQ

What is the best approach to solve the Minesweeper problem?

The best approach is using Depth-First Search (DFS) combined with array manipulation to reveal cells and calculate adjacent mine counts.

How do you handle edge cases in the Minesweeper problem?

You handle edge cases by carefully checking the boundaries of the grid during DFS traversal and ensuring that all neighboring cells are correctly processed.

Can the Minesweeper problem be solved using Breadth-First Search (BFS)?

Yes, BFS can be used as an alternative to DFS. BFS is especially useful when you want to process all adjacent cells level by level.

What is the time complexity of solving the Minesweeper problem?

The time complexity is O(m * n), where m and n are the dimensions of the board, because in the worst case, all cells must be visited.

How does GhostInterview assist in solving the Minesweeper problem?

GhostInterview provides detailed steps for implementing DFS, guides you through efficient grid traversal, and helps you handle edge cases in Minesweeper.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        def dfs(i: int, j: int):
            cnt = 0
            for x in range(i - 1, i + 2):
                for y in range(j - 1, j + 2):
                    if 0 <= x < m and 0 <= y < n and board[x][y] == "M":
                        cnt += 1
            if cnt:
                board[i][j] = str(cnt)
            else:
                board[i][j] = "B"
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < m and 0 <= y < n and board[x][y] == "E":
                            dfs(x, y)

        m, n = len(board), len(board[0])
        i, j = click
        if board[i][j] == "M":
            board[i][j] = "X"
        else:
            dfs(i, j)
        return board

Continue Practicing

#463 island perimeter #417 pacific atlantic water flow #695 max area of island