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 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
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.
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
- Minimum Forward Jumps Medium Free Cross a jump array with the fewest hops, including dead ends, without enumerating every reachable edge.
- Rotting Oranges Medium Free How many minutes until the rot spreads everywhere?
- Shortest Path in Binary Matrix Medium Free Shortest 8-directional path across an open grid - DFS wanders, BFS knows.
- Longest Cycle in a Functional Graph Hard Free Find the largest directed cycle without retracing every path.