Number of Islands in a 2d grid

Recently, I've solved this "Number of Islands" problem on LeetCode, the solution was accepted by the LeetCode OJ.

Problem Description


Given a 2d grid map of '1's (land) and '0's (water), count the number
of islands. An island is surrounded by water and is formed by
connecting adjacent lands horizontally or vertically. You may assume
all four edges of the grid are all surrounded by water.

Examples/Test Cases

A single island:

11110
11010
11000
00000

3 islands:

11000
11000
00100
00011

The Solution

The idea behind the solution posted below is to:

• iterate over every cell of the grid

• when find a 1 value, increment the island counter, use the BFS to find all cells in the current island

• mark all the cells in the current island with value 2

The Code:

```
from collections import deque

class Solution(object):
def append_if(self, queue, x, y):
"""Append to the queue only if in bounds of the grid and the cell value is 1."""
if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]):
if self.grid[x][y] == '1':
queue.append((x, y))

def mark_neighbors(self, row, col):
"""Mark all the cells in the current island with value = 2. Breadth-first search."""
queue = deque()

queue.append((row, col))
while queue:
x, y = queue.pop()
self.grid[x][y] = '2'

self.append_if(queue, x - 1, y)
self.append_if(queue, x, y - 1)
self.append_if(queue, x + 1, y)
self.append_if(queue, x, y + 1)

def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""

if not grid or len(grid) == 0 or len(grid[0]) == 0:
return 0

self.grid = grid

row_length = len(grid)
col_length = len(grid[0])

island_counter = 0
for row in range(row_length):
for col in range(col_length):
if s

One way to simplify the problem is a shift of datastructure to hold your islands. By converting the grid to a set containing only the "land" parts, you can speed up the computation by entirely removing the check for "does it fit into the map". The idea here is to pick a land in your set — doing so you'll know that you have discovered a new island — and remove all land connected to it in your set. Luckily set.remove is easy to use and let us know if the element was present or not so we can stop the recursion.

I would also advise against using explict len to iterate over the grid. enumerate should give you anything you need in a more cleaner way.

Lastly, in the testing code, grid is

[['1', '1', '0', '0', '0'],
 [' ', ' ', ' ', ' ', '1', '1', '0', '0', '0'],
 [' ', ' ', ' ', ' ', '0', '0', '1', '0', '0'],
 [' ', ' ', ' ', ' ', '0', '0', '0', '1', '1']]

So you might have some inexpected results. I suggest the use of the textwrap module like so:

if __name__ == '__main__':
    from textwrap import dedent
    grid = dedent("""\
        11000
        11000
        00100
        000111""")
    ...

Revised algorithm would look like:

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        # Convert the grid to a bag of land
        self.lands = {
            (row, col)
            for row, line in enumerate(grid)
            for col, land in enumerate(line)
            if land == '1'
        }

        island_counter = 0
        # Remove islands from the bag one by one
        while self.lands:
            island_seed = next(iter(self.lands))  # pick a random land
            island_counter += 1
            self.remove_island(island_seed)

        return island_counter

    def remove_island(self, coordinates):
        try:
            self.lands.remove(coordinates)
        except KeyError:
            return

        x, y = coordinates
        self.remove_island((x - 1, y))
        self.remove_island((x + 1, y))
        self.remove_island((x, y - 1))
        self.remove_island((x, y + 1))

If you don't like remove_island being recursive, you can still write it as a BFS as you did in your solution. But since you’re not poping from the left, there is no need of a deque:

def remove_island(self, coordinates):
        queue = [coordinates]
        while queue:
            x, y = queue.pop()
            try:
                self.lands.remove((x, y))
            except KeyError:
                pass
            else:
                queue += [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]

StackExchange Code Review Q#157394, answer score: 8