Count islands in a grid
Count connected groups of land cells in a grid where land connects vertically and horizontally but not diagonally.
Course progress
Problem 98 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
grid rows = ["11000", "11000", "00100", "00011"]
Expected output
3
What is happening?
The top-left block, center cell, and bottom-right pair are disconnected from one another, so the grid contains three islands.
Solution strategy
Build the right mental model
When an unvisited land cell appears, count a new island and recursively mark every connected land cell as visited.
Core concepts
grid · depth-first search
Complexity
Time O(rows x columns), call-stack space O(rows x columns) in the worst case.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for number-of-islands
using System;
class Program
{
static void Visit(char[,] grid, int row, int column)
{
if (row < 0 || row >= grid.GetLength(0) || column < 0 ||
column >= grid.GetLength(1) || grid[row, column] != '1') return;
grid[row, column] = '0';
Visit(grid, row - 1, column); Visit(grid, row + 1, column);
Visit(grid, row, column - 1); Visit(grid, row, column + 1);
}
static int CountIslands(char[,] grid)
{
int count = 0;
for (int row = 0; row < grid.GetLength(0); row++)
for (int column = 0; column < grid.GetLength(1); column++)
if (grid[row, column] == '1') { count++; Visit(grid, row, column); }
return count;
}
static void Main()
{
char[,] grid = {
{ '1', '1', '0', '0', '0' }, { '1', '1', '0', '0', '0' },
{ '0', '0', '1', '0', '0' }, { '0', '0', '0', '1', '1' }
};
Console.WriteLine(CountIslands(grid));
}
}Knowledge check
Questions students often ask
What is the main idea behind count islands in a grid?
When an unvisited land cell appears, count a new island and recursively mark every connected land cell as visited.
What is the time and space complexity of this solution?
Time O(rows x columns), call-stack space O(rows x columns) in the worst case.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.