Minesweeper - Solution & Explanation

Problem Overview: You’re given a Minesweeper board and a click position. If the clicked cell contains a mine, the game ends. Otherwise, reveal cells according to classic Minesweeper rules: show the number of adjacent mines, or recursively reveal neighboring cells when the count is zero.

Approach 1: Depth-First Search (DFS) Flood Fill (Time: O(m*n), Space: O(m*n))

This problem is essentially a flood-fill traversal on a matrix. When the clicked cell is empty ('E'), count mines in the 8 neighboring cells. If the count is non‑zero, update the cell with that number and stop expanding. If the count is zero, mark it as 'B' and recursively explore all 8 neighbors using Depth-First Search. Each cell is processed at most once, so the traversal runs in O(m*n) time with recursion stack up to O(m*n) in the worst case.

The key insight: only expand when the adjacent mine count is zero. That rule prevents unnecessary exploration and mirrors how the real Minesweeper game reveals empty regions.

Approach 2: Breadth-First Search (BFS) Expansion (Time: O(m*n), Space: O(m*n))

The same logic can be implemented iteratively with a queue using Breadth-First Search. Start by pushing the clicked cell into the queue. For each cell popped, count adjacent mines. If the count is greater than zero, write the number and stop expansion from that cell. If the count is zero, mark it as 'B' and enqueue all neighboring unrevealed cells.

BFS processes cells level by level and avoids recursion depth issues. The queue may temporarily hold many cells during large empty-region expansions, but overall complexity remains O(m*n) time and O(m*n) space because each cell enters the queue at most once.

This version is often preferred in production systems where recursion limits are a concern.

Recommended for interviews: Either DFS or BFS is acceptable since both represent the same flood-fill idea with O(m*n) complexity. Interviewers typically expect you to recognize the grid traversal pattern quickly and implement DFS first because it’s shorter. Explaining that BFS avoids recursion depth limits demonstrates stronger problem‑solving awareness.