InternDoor

Count the islands

Mediumgraphs · depth-first search · breadth-first search · grids

Reported in interviews at (where)

A map is drawn on a grid: '1' is land and '0' is water. Land cells that touch on a side (up, down, left or right, never corner to corner) belong to the same island. Everything beyond the grid's edge is water.

Return how many islands the map has.

Example 1
Input
grid = [["1","1","0","0"],["1","0","0","1"],["0","0","1","1"]]
Output
2

The top-left block is one island; the right side (rows 2 and 3) is another.

Example 2
Input
grid = [["1","0","1"],["0","1","0"],["1","0","1"]]
Output
5

Corners do not join cells, so every 1 is its own island.

Limits

  • 1 <= grid.length, grid[i].length <= 300
  • grid[i][j] is '0' or '1'.

Hints

Hint 1

Walk the grid; at each land cell not seen yet, count one island and flood-fill everything it reaches.

Hint 2

A queue (BFS) avoids running out of stack on a huge island.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.