Island Count

Island Count determines the number of connected components, commonly called "islands," in a 2D binary grid. Each island is a group of adjacent land cells connected horizontally or vertically, surrounded by water cells. The algorithm systematically scans the grid and uses flood fill to mark each distinct island as it is discovered. This problem is one of the most popular introductory graph problems in computer science education and coding interviews, appearing on platforms like LeetCode (Problem 200), HackerRank, and in textbooks on algorithms. Despite its simplicity, the Island Count pattern generalizes to a powerful technique for analyzing connected components in any grid-based or graph-based structure.

How It Works

1. Scan: Iterate through every cell in the grid row by row, left to right. This systematic scan ensures no cell is overlooked.
2. Discover island: When an unvisited land cell is found, it represents the discovery of a new island that has not been counted yet. Increment the island counter by one.
3. Flood fill: Starting from the newly discovered land cell, initiate a BFS or DFS traversal to visit all connected land cells. Mark each visited cell so it will not be counted again. The fill propagates to all 4-connected neighbors (up, down, left, right) that are land cells and have not been visited. This process traces the entire boundary and interior of the island.
4. Continue scanning: After the flood fill completes and the entire island has been marked, resume the row-by-row scan from where it left off. Any subsequent land cell encountered will either have been already visited (part of a previously counted island) or will trigger a new island discovery.
5. Result: When the scan reaches the end of the grid, the island counter holds the total number of connected components. Each island has been discovered exactly once and fully explored via flood fill.

Implementation Choices

The flood fill step can use BFS with a queue or DFS with a stack (or recursion). BFS explores the island in expanding layers from the discovery point, while DFS dives deep along one path before backtracking. Both produce the same result and have the same time complexity. For marking visited cells, there are two approaches: modifying the grid in place (changing land cells to water or a sentinel value) or maintaining a separate boolean visited matrix. In-place modification saves memory but mutates the input, which may not be acceptable in all contexts. The visited matrix approach preserves the original grid at the cost of O(N x M) additional space.

Variations and Extensions

The basic island count problem has many interesting variations. 8-connected islands consider diagonal adjacency, which can merge islands that appear separate under 4-connectivity. This changes the problem significantly, as islands that were disconnected become connected through diagonal links. Island perimeter asks for the total boundary length of all islands rather than the count. Max island area asks for the size of the largest connected component. Number of distinct islands asks how many unique island shapes exist (considering translation but not rotation). Dynamic island count handles a grid where land cells are added one at a time, requiring efficient Union-Find to maintain the component count without rescanning the entire grid. Each variation builds on the same fundamental pattern of grid traversal combined with connected component discovery.

Complexity

Each cell is visited exactly once during the row-by-row scan and at most once during flood fill, yielding linear time in the grid size. The space is O(N x M) for the visited matrix (or implicitly through grid modification) plus the maximum size of the BFS queue or DFS stack, which in the worst case (a grid entirely of land forming one giant island) is O(N x M). For a grid with many small islands, the practical space usage of the queue or stack is much smaller.

Connection to Graph Theory

Island Count is a specific instance of the general connected components problem in graph theory. Each land cell is a vertex, and edges connect adjacent land cells. The algorithm effectively computes the number of connected components in this implicit graph. On general graphs represented as adjacency lists, the same technique applies: scan all vertices, and when an unvisited vertex is found, run BFS or DFS to explore its entire component. The grid structure simply provides a convenient implicit adjacency representation where neighbors are determined by coordinate arithmetic rather than explicit edge lists. Understanding this connection is valuable because it shows that grid problems and graph problems are fundamentally the same, just with different representations.

When to Use

Island counting and connected component analysis appear in many real-world domains. In image segmentation, distinct objects in a binary image are identified by counting connected regions of foreground pixels. In geographic information systems, satellite imagery is analyzed to count landmasses, lakes, or forest patches. Medical imaging uses connected component analysis to identify tumors or lesions in scan data. In network analysis, counting disconnected clusters reveals the structure of communication networks or social graphs. PCB design tools use it to identify separate copper regions on circuit boards. Game developers use island counting for procedural map generation, verifying that all rooms in a dungeon are reachable, or detecting isolated regions that need connecting. The technique is also a stepping stone to more advanced graph algorithms like finding articulation points and bridges, which identify cells or connections whose removal would change the island count.