Skip to content
Katabench
Try free

Number of Islands

Medium About 20 min Free, no account needed

Count the connected patches of land in a grid.

The brief

Given a grid of 1 (land) and 0 (water), count the islands, groups of land cells connected horizontally or vertically.

The performance bar

The obvious approach labels every land cell uniquely, then repeatedly sweeps the grid letting labels "flow" to the minimum of their neighbors until nothing changes, O(cells * diameter). The hidden test is a 200x200 serpentine island whose diameter is ~20,000 cells, so the repeated sweeps are too slow. You will need an approach that visits each cell a bounded number of times, O(cells).

Starter code

C#
using System;

public class Solution
{
    // TODO: return the number of 4-connected groups of 1s.
    public int NumIslands(int[][] grid)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Depth-first search
Recurse or use an explicit stack to explore connected regions, paths and components.
Breadth-first search
Explore a graph or grid level by level for shortest unweighted distances and spreading processes.

Do these first

Related katas