PPractick

The problem

A satellite image is a grid where '1' is land and '0' is water. For a coastline survey, two land cells belong to the same island if they touch horizontally, vertically or diagonally (8 directions). Count the islands. Each island is a connected component of land cells. Scan the grid, and every time you find land that hasn't been visited, count a new island and flood-fill it with BFS or DFS over all 8 neighbours, marking it visited.

Example: grid 0111000 / 0011010 → 2.

Function signature

int numIslands8(const vector<string>& grid);  // '1' land, '0' water; 8-directional

Test cases

Input (rows)	Output	Explanation
01 / 10 / 11 / 10	1	The diagonal joins the top 1 to the rest
0111000 / 0011010	2	The single 1 at the far right is separate
101 / 010 / 101	1	All joined through the centre diagonally
100 / 001	2	Not adjacent, even diagonally
000	0

(Confirm: adjacency includes the four diagonals; the grid may be non-square.)

How interviewers phrase it

• "Given a grid of '0's and '1's, find the number of islands, where cells connected horizontally, vertically or diagonally form one island" (GeeksforGeeks "Find the number of islands").
• LeetCode 200 is the same with only 4-directional connectivity.

Clarifying questions to ask

1. 4 or 8 directions? (8 here.)
2. May I modify the grid to mark visited cells? (If yes, no visited array is needed.)
3. How large is the grid? (Up to 500 × 500, so recursion could get deep: prefer BFS.)

Follow-ups to expect

1. "How do you enumerate 8 neighbours?"
2. "Why BFS instead of recursive DFS?"
3. "DSU alternative?"
4. "What changes for 4 directions?"
5. "Complexity?"

Related questions

• Connected Components Medium
• Traversal Techniques Medium
• Number of provinces Medium
• Flood fill algorithm Medium
• Surrounded Regions Medium
• Number of enclaves Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in