Compute island size in grid

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute Island Size in Grid

Given an m x n binary matrix grid of 0s (water) and 1s (land), an island is a maximal group of 1s connected 4-directionally (up, down, left, right). Implement sizeOfIsland(grid, r, c) that returns the number of cells in the island that contains cell (r, c). Return 0 if (r, c) is water or out of bounds.

Use DFS (iterative stack) flood-fill from the starting cell, tracking visited cells with an auxiliary visited set so the input grid is not mutated. Base cases: return 0 immediately when the grid is empty, when (r, c) is outside the matrix, or when the starting cell is water. Otherwise expand to all 4-directionally connected land cells, counting each cell once.

Constraints

• 1 <= m, n (grid may also be empty: [] or [[]])
• grid[i][j] is 0 or 1
• r and c may be any integer (out-of-bounds returns 0)
• Islands are connected 4-directionally only (no diagonals)

Examples

Example 1

Input: ([[1,1,0],[0,1,0],[0,0,1]], 0, 0)
Output: 3

Explanation: Cells (0,0),(0,1),(1,1) form one connected island of size 3.

Example 2

Input: ([[1,1,0],[0,1,0],[0,0,1]], 2, 2)
Output: 1

Explanation: Cell (2,2) is an isolated land cell; its island has size 1.

Hints

1. The base cases are the tricky part: handle empty grid, out-of-bounds (r, c), and water at the start before doing any traversal.
2. Use an explicit stack (iterative DFS) or a queue (BFS) to flood-fill. Mark a cell visited the moment you push it, not when you pop it, to avoid double-counting.
3. An auxiliary visited set keeps the input grid immutable; alternatively you could temporarily flip 1s to 0s, but state the trade-off.

Largest Island in the Grid (Follow-up)

Follow-up to the island-size problem. Given an m x n binary matrix grid of 0s (water) and 1s (land) where islands are groups of 1s connected 4-directionally, return the size of the largest island in the entire grid. Return 0 if there is no land.

Scan every cell; whenever you reach an unvisited land cell, run a DFS/BFS flood-fill to measure that whole island, track the maximum size seen, and continue. A 2D visited matrix ensures each cell is counted exactly once across all islands, keeping the overall pass linear in the number of cells.

Constraints

• 1 <= m, n (grid may also be empty: [] or [[]])
• grid[i][j] is 0 or 1
• Islands are connected 4-directionally only (no diagonals)
• Return 0 when the grid contains no land

Examples

Example 1

Input: ([[1,1,0],[0,1,0],[0,0,1]],)
Output: 3

Explanation: Largest island is the size-3 cluster at the top-left; the lone (2,2) cell has size 1.

Example 2

Input: ([[0,0],[0,0]],)
Output: 0

Explanation: No land in the grid, so the largest island size is 0.

Hints

1. Reuse the single-island flood-fill, but call it from a double loop over every cell, skipping cells you have already visited.
2. A shared visited matrix across the whole scan guarantees O(m*n) total work — you never re-traverse a counted island.
3. Track the running maximum island size; the answer is 0 if every cell is water.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Model each reachable configuration as a graph state and choose the traversal by edge cost: BFS for unweighted shortest paths, Dijkstra for non-negative weighted paths, or topological DP for DAGs. Track visited states at the correct granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.