Number of Islands

Graphsmedium

Given a `grid` of `1`s (land) and `0`s (water), implement `numIslands(grid)` returning the number of islands. An island is a group of `1`s connected horizontally or vertically.

Examples

Input: [[1,1,0],[0,1,0],[0,0,1]]

Output: 2

The top-left L-shape is one island; the bottom-right cell is another.

Input: [[0,0],[0,0]]

Output: 0

Sample tests

Input: numIslands([[1,1,0],[0,1,0],[0,0,1]])

Output: 2

Input: numIslands([[0,0],[0,0]])

Output: 0

+ 2 hidden tests run on Submit.

Hints

Common pitfalls

Forgetting to mark visited cells turns one island into an infinite loop or an over-count.

Learning resources

Wikipedia: Depth-first search

Approach & explanation (try first)

Each time the scan meets land that has not been flooded, it is the start of a fresh island; a DFS then sinks the whole connected component. Every cell is visited a constant number of times, so it runs in O(rows × cols).

⌘/Ctrl + Enter

Run your code to see results.

← Back to problems

Number of Islands

Graphsmedium

Given a `grid` of `1`s (land) and `0`s (water), implement `numIslands(grid)` returning the number of islands. An island is a group of `1`s connected horizontally or vertically.

Examples

Input: [[1,1,0],[0,1,0],[0,0,1]]

Output: 2

The top-left L-shape is one island; the bottom-right cell is another.

Input: [[0,0],[0,0]]

Output: 0

Sample tests

Input: numIslands([[1,1,0],[0,1,0],[0,0,1]])

Output: 2

Input: numIslands([[0,0],[0,0]])

Output: 0

+ 2 hidden tests run on Submit.

Hints

Common pitfalls

Forgetting to mark visited cells turns one island into an infinite loop or an over-count.

Learning resources

Wikipedia: Depth-first search

Approach & explanation (try first)

⌘/Ctrl + Enter

Run your code to see results.