Compute island size in grid
AppleSoftware Engineer · Technical ScreenLast updated
This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute island size in grid states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given an m x n binary matrix grid of 0s (water) and 1s (land), where an island is a group of 1s connected 4-directionally, implement sizeOfIsland(grid, r, c) that returns the number of cells in the island containing cell (r, c); return 0 if (r, c) is water or out of bounds. You may either mutate grid (e.g., marking visited) or use an auxiliary visited structure—explain your choice. Describe the algorithm (DFS or BFS), clearly state the base cases, and analyze time and space complexity. Follow-up: adapt your solution to compute the size of the largest island in the entire grid.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.