Count Islands and Return the Largest Island Size

Given a two-dimensional land/water grid, return both the number of islands and the size of the largest island. An island is a maximal group of land cells connected horizontally or vertically.

Implement island_stats(grid: int[][]) -> int[] and return [island_count, largest_size].

Constraints & Assumptions

• The grid is rectangular, with 1 through 500 rows and columns.
• Every entry is 0 for water or 1 for land. Diagonal contact does not connect islands.
• If there is no land, return [0, 0].
• Each land cell contributes once to exactly one island's size.
• You may use DFS or BFS. Account for a large single island when choosing recursive versus iterative traversal.
• The combined two-integer output and four-neighbor definition make the reported island-count and maximum-size follow-up one deterministic practice task.

Examples

grid = [[1,1,0],[0,1,0],[1,0,1]]
result = [3,3]

grid = [[0,0],[0,0]]
result = [0,0]

Alongside the implementation, compare DFS and BFS for this grid: describe their traversal order, give the time and auxiliary-space bounds for each, and explain the recursion-stack risk of recursive DFS on a large island. Distinguish the visited-state storage from the explicit stack or queue, and explain how the same traversal obtains both the island count and the maximum component size.

Hint: Count when starting a new traversal

An unvisited land cell starts one island. Track how many land cells that traversal reaches, then compare that component size with the current maximum.

Count Islands and Find the Largest Island

Hints

1. An unvisited land cell begins a new island; count the cells reached by that traversal to obtain its size.

Approach

Scan the grid in row order. Whenever an unvisited land cell is found, increment the island count and traverse its four-neighbor land component with an explicit DFS stack. Mark a cell when pushing it, so two already-reached neighbors cannot schedule it twice. Count each popped cell, then compare that component size with the maximum.

The traversal reaches only cells connected to its start. Conversely, any connected land cell has a path from the start, and repeatedly exploring every four-neighbor edge reaches all cells along that path. Marking on discovery makes the counted cells distinct. Thus each traversal counts exactly one maximal component, and the outer scan eventually starts exactly one traversal per island. The component counts give both requested statistics. When no land is present neither count is updated, yielding [0,0]. Diagonals never enter the neighbor list.

DFS takes the most recently discovered pending cell, exploring branches deeply; BFS uses a FIFO queue and explores cells by shortest unweighted distance from the component's start. Both inspect each cell and at most four neighbors, taking O(RC) time. With a separate visited matrix, visited-state storage is O(RC) for either traversal. The explicit DFS stack or BFS queue can additionally use O(RC) space in the worst case, so each has O(RC) total auxiliary space; the bounds describe separate stores rather than treating the queue or stack as the visited matrix. Recursive DFS can have call depth proportional to the number of land cells, for example on a long thin island, and overflow the language runtime's call stack. This iterative implementation avoids recursive call depth. BFS would produce the same count and maximum size because only component membership, not visitation order, determines them.

• Time complexity: O(R*C)
• Space complexity: O(R*C) for visited state and the explicit traversal stack