Calculate the Largest Island in a 2D Integer Array
Question description
Suppose there is an n * n two-dimensional image, where 1 represents "land" and 0 represents empty space. Please design an algorithm to calculate the largest piece of land in the image, that is, the sub-image with the most 1s.
For example:
[[0,0,0,0,0,0,0,0,0,0],
[0,1,1,1,0,0,0,1,0,0],
[0,0,1,1,0,0,0,0,0,0],
[0,0,0,1,0,0,0,1,0,0],
[0,0,0,0,0,0,1,0,1,0],
[0,0,0,1,0,0,0,1,0,0],
[0,0,1,1,1,0,0,1,0,0],
[0,1,1,1,1,1,0,1,0,0],
[0,0,1,1,1,0,0,1,0,0],
[0,0,0,0,0,0,0,0,0,0]
]The largest island is 12.
This problem asks for the size of the largest connected region of 1s in an n*n grid. The standard solution is to scan the matrix, and whenever an unvisited land cell is found, use DFS or BFS to explore its four-directionally connected neighbors, count the island size, and keep track of the maximum. A visited set or in-place marking prevents double counting. The key interview focus is grid traversal, connected-component search, and clean implementation of a graph-search template.
