Explore the Island at a Given Cell With BFS, Then Count Lakes Enclosed by Land

A satellite image is given as an `N × M` grid of characters, where `'X'` is land and `'.'` is water. You are also given the coordinate `(r, c)` of one cell in the grid. The exercise has two parts: first traverse connected land with breadth-first search (BFS), as in the classic island-counting problem, then extend the solution to find lakes. ```text grid (rows 0 to 4, columns 0 to 8): row 0 ......... row 1 .XXXXX... row 2 .X.X.X.X. row 3 .XXXXX... row 4 .......XX (r, c) = (1, 1) Part 1: the island containing (1, 1) has 13 land cells Part 2: that island encloses 2 lakes, the single water cells (2, 2) and (2, 4) ``` ### Constraints and Clarifications - Assume that land cells belong to the same island when they share a side (up, down, left or right), as in the classic island-counting problem; land cells that touch only at a corner are not connected. - The interview did not specify the grid size, what the traversal should return, or the exact definition of a lake. Settle these with the interviewer. ### Clarifying Questions - What should Part 1 return: the island's cells, its size, or the number of islands in the whole grid? - What should happen if `(r, c)` is water, or outside the grid? - How large can the grid be, and is recursion depth a concern? ### Part 1 — Traverse the island containing (r, c) Starting from `(r, c)`, use BFS to visit every land cell of the island that contains it, and return those cells. Then explain how the same traversal counts all the islands in the grid. ```hint Mark cells early Decide whether a cell is marked as visited when it is added to the queue or when it is taken out, and what goes wrong with the other choice. ``` #### What This Part Should Cover - A correct BFS with bounds checks and visited marking - Time and space complexity in terms of N and M - Edge cases: `(r, c)` on water, an island touching the grid edge, a grid that is entirely land - Extending the traversal to count every island in the grid ### Part 2 — Count the lakes enclosed by land Follow-up: how would you identify and count the inland lakes, bodies of water completely surrounded by land? Define a lake precisely, describe the approach, and implement it. ```hint Start from what is certainly not a lake Some water obviously belongs to the open sea. Consider whether finding that water first makes the remaining question easier. ``` ```hint Diagonal gaps Draw two land cells that touch only at a corner, with water on both sides of that corner, and decide whether water can pass between them. ``` #### Clarifying Questions for this Part - Does water on the edge of the image count as a lake, or could it continue beyond the image? - Can water pass through a gap where two land cells touch only at a corner? - Should a lake count only if it is enclosed by the island containing `(r, c)`, or does any enclosed water in the image count? - If a lake contains a smaller island with a pond of its own, how many lakes does the outer island have? #### What This Part Should Cover - A precise lake definition that is consistent with the land connectivity rule - An algorithm that separates enclosed water from water connected to the outside, and counts each lake exactly once - Complexity, and edge cases: lakes of several cells, water on the border, islands inside lakes ### What a Strong Answer Covers - Settles the traversal output and the lake definition before coding - Clean, iterative BFS code that both parts reuse - Linear time in the grid size for both parts, with the memory use stated - Small hand-made test grids that exercise each edge case, including a diagonal gap ### Follow-up Questions - The image is too large for memory and arrives one row at a time. How do you count the islands? - Return the number of lakes of every island in one pass, instead of only the island at `(r, c)`. - Return the area of the largest lake instead of the count. - Water cells are turned into land one at a time. How do you keep the island count up to date after each change?