</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

Graph Real-Life Problems

What is this?

Most graph problems make you find the algorithm. This one hands it to you (it is a flood fill) and then makes the rules the difficulty. Clicking a square in Minesweeper does one of three things depending on what is underneath and what surrounds it, and only one of those three continues the flood.

Getting this right is a test of reading comprehension and case discipline rather than algorithmic insight, which is exactly why it appears in interviews.

Minesweeper reveal flowchart: count adjacent mines before recursing

Why the numbers matter: a numbered square stops the flood. If revealing a square with adjacent mines also revealed its neighbours, one click would uncover most of the board and there would be little left to deduce. The numbers are the walls of the flood fill, and the single "do not recurse" branch is what keeps them walls.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.


Core idea: the traversal is an ordinary 8-directional flood fill. The problem is entirely in the branch structure: count first, then decide whether to recurse, and in remembering that a numbered cell is a wall, not a doorway.


1. Count before you recurse

The single most common wrong implementation recurses first and counts afterwards. The order must be:

def reveal(board, r, c):
    if board[r][c] == 'M':
        board[r][c] = 'X'                    # hit a mine, stop entirely
        return

    mines = count_adjacent_mines(board, r, c)   # count BEFORE deciding
    if mines > 0:
        board[r][c] = str(mines)                # a wall, do not expand
        return

    board[r][c] = 'B'                            # empty, expand
    for dr, dc in EIGHT_DIRECTIONS:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc) and board[nr][nc] == 'E':
            reveal(board, nr, nc)

Three exits, and only the last one recurses. The guard board[nr][nc] == 'E' doubles as the visited check: once a cell has been changed to B or a digit it is no longer E, so it will not be processed twice. No separate visited set is needed because the board is mutated in place. (count_adjacent_mines and in_bounds are small helpers; the lesson has the full runnable version.)

2. Eight directions, not four

Adjacency here includes diagonals, so both the mine count and the expansion use all eight offsets:

EIGHT_DIRECTIONS = [(-1,-1), (-1,0), (-1,1),
                    ( 0,-1),         ( 0,1),
                    ( 1,-1), ( 1,0), ( 1,1)]

Writing four directions by habit produces a board that looks almost right and is wrong along every diagonal, the kind of bug that passes a small test and fails a large one.


3. A 30-second worked example

board            click (3,0), which is 'E' with no adjacent mines
E E E E E
E E M E E        after revealing:
E E E E E        B 1 E 1 B
E E E E E        B 1 M 1 B
                 B 1 1 1 B
                 B B B B B

The flood spreads through every empty cell but stops at the ring of numbered cells around the mine. Those cells are revealed and show their counts, but they are not expanded through. That is why the cell above the mine, which touches only numbered cells, is never reached and stays E.


4. Where you'll actually meet this

  • Game development. Revealing a connected blank region in a tile game is a conditional flood fill.
  • Image editing. The paint-bucket tool spreads from a seed pixel while a condition holds. The condition is colour similarity rather than a mine count, but the structure is the same.
  • Connected regions on a grid. Labelling blobs in a binary image uses the same neighbour loop, often with 8-connectivity.

5. Problems in this chapter

Minesweeper

This is LeetCode 529. Reveal a board given a click. Mine becomes X; a cell with adjacent mines shows the count and stops; an empty cell becomes B and expands to all eight neighbours.
Pattern: conditional 8-directional flood fill. Target: O(mn) time (each cell is revealed once and does an 8-neighbour count), O(mn) recursion depth or queue size in the worst case.


6. Common pitfalls

  • Recursing before counting. The count decides whether to recurse at all; doing it the other way round floods the whole board.
  • Using four directions. Minesweeper adjacency is all eight, for both the count and the expansion.
  • Expanding through numbered cells. They are revealed but never recursed into. This is the rule the whole game depends on.
  • Forgetting the mine case. A click directly on a mine sets X and does nothing else.
  • Adding a visited set. Unnecessary: mutating E into B or a digit already prevents reprocessing.
  • Missing bounds checks in the diagonal offsets. Corners are where the index errors live.
  • Recursion depth on a large empty board. An entirely empty grid can recurse m × n deep, up to 2,500 on a 50 x 50 board, past Python's default limit of 1,000. Use an explicit queue or stack.

7. Key takeaways

  1. The algorithm is the easy part. Read the specification twice; the branches are the problem.
  2. Count first, then decide. The mine count determines whether this cell is a wall or a doorway.
  3. Numbered cells stop the flood. Without that rule one click could uncover most of the board.
  4. Eight directions, consistently, in both the count and the expansion.
  5. Mutation can serve as the visited set when the problem lets you write into the input.
  6. Watch the recursion depth on large uniform grids.
  7. Why interviewers like it: it is deliberately unglamorous. It measures whether you implement a stated specification exactly, which is most of the job.

Order: Minesweeper.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.