Number of Islands in a 2d grid

Question

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 self.grid[row][col] == '1':
                    # found an island
                    island_counter += 1

                    self.mark_neighbors(row, col)

        return island_counter


if __name__ == '__main__':
    grid = """11000
    11000
    00100
    00011"""

    grid = [list(line) for line in grid.splitlines()]
    print(Solution().numIslands(grid))

The Questions:

Is it the most optimal solution to the problem, or is there a more efficient approach? What would you improve code-quality or code-organization wise?

Answer 1

Complexity

Each cell will be accessed at most 5 times (once to check itself, once per each neighbour that are on land, as part of their BFS search).

This means your overall complexity is O(n) (n being the total number of cells). so your algorithm has optimal complexity.

Another way to come to this conclusion is to note that BFS is optimal for flood-filling an area, and you're flood-filling each island once and once only, while water cells are scanned and skipped.

---

Optimization

There are a few things to do to speed-up the algo. One is to use the borders as the Problem statement hinted at:

You may assume all four edges of the grid are all surrounded by water

It is common practice to load up your map in an (w+2)x(h+2) area (w and h being width and height), and fill the borders with water (0s in your case).

While this doesn't change much the complexity (O((w+2)x(h+2)) ~ O(n)), this allows you to ommit bounds checking like you do in append_if method.

To leverage this boundary, you iterate on the inside (x = 1..w & y = 1..h), so you omit x = 0, y =0, x = w+1, y = h + 1 in the double-for search. The gain is that when accessing a cell's neighbours you'll have the guarantee that x-1, x+1, y-1 and y+1 are never out of bounds. This saves a lot of conditions computing and ifs.

This also allows you to inline access instead of extracting it in a method call due to its increased simplicity. This means even less overhead.

---

Using a dict

If the map was a dict: cellPosition -> CellType, you'd have the ability to remove the cells uncovered by BFS from the map altogether, which would prevent you from checking them later in your scanning loop. But that's a very small optimization, also access would be slower so I don't think it's worth it.

---

Code Clarity

Very easy code to follow.

Comments are good.

Naming is spot on. Solution could have been IslandCounter, but I suppose it's a limitation of the website.

I didn't understand that part:

    """
    :type grid: List[List[str]]
    :rtype: int
    """

But I'm a non-native python coder, so I'll let others chime in.

Answer 2

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)]

Answer 3

It seems that someone has copied @MathiasEttinger's answer claiming it as their own and posted another question on CR asking for feedback on "their" solution. So here are my improvements to @MathiasEttinger's solution (originally posted here):

Overall this code is pretty good. Well organized, sufficient commenting, good spacing, good use of pythonic patterns (comprehensions, try/catch, etc). So, most of the issues I see are just nitpicks:

• Use Python 3 (so class Solution(object): should be class Solution:)
• PEP8 - I think you only have one name that doesn't meet its standards (numIslands should be num_islands)
• I would actually call num_islands, in the context of a Solution, count_islands
• If you're going to document the types why not use Python optional typing and actually document what the function does in the doc comment?
• You should write some good unit tests for this, so that you can refactor with confidence
• You don't need to do list() on a string, it is already a sequence
• We usually don't break comprehensions onto separate lines like that, something like the following is usually preferred:

self.lands = {(row, col)
              for row, line in enumerate(grid)
              for col, land in enumerate(line) if land == '1'}

• remove_island should be _remove_island (it's a private method)
• Your use of next(iter(self.lands)) is a little strange given that you could do self.lands.pop() (which returns and removes one of the coordinates). I would move things around a little so that you do this inside your remove_island so that your use of it could just be while remove_island(self.lands): num_islands += 1
• I'm not super convinced you need a Solution class. An object for this seems a tad unnecessary. A function count_islands(grid: str) -> int that calls a remove_islands(lands: Set[Tuple[int, int]]) -> bool should do
• Having said that, one thing from a design perspective that you might consider is that your solution handles two concerns: it parses the grid and then counts the islands. Ideally you only want that part of the code to be responsible for the latter (what if there are parsing errors to handle? what if other algorithms need access to this grid? what if you want to switch to a 3D grid? All of these would require changes to code that also handles counting islands, which isn't ideal). In this vein, I would create a Grid class that can parse itself (via class method) and a Point class (namedtuple) that understands the grid system. For now, it's sufficient to just add a num_islands property to Grid but later you may find you want to extract that out into a function like count_islands(grid: Grid) -> int. You could even go as far as defining your own PointSet capable or remove_any_island and remove_island_containing.

The less object oriented refactoring:

from textwrap import dedent
from typing import Set, Tuple


Point = Tuple[int, int]


def count_islands(grid: str):
    """
    Counts the number of contiguous islands in a 2D grid (where the islands
    are represented by 1's and ocean is represented by 0's).
    """

    # Collect all land points in the grid
    land_points = {(x, y) for y, line in enumerate(grid.splitlines())
                          for x, land in enumerate(line) if land == '1'}

    num_islands = 0

    # Remove islands until there are none left
    while _remove_island(land_points):
        num_islands += 1

    return num_islands

def _remove_island(land_points: Set[Point], point: Point = None):
    try:
        if point is not None:
            x, y = point
            land_points.remove(point)
        else:
            x, y = land_points.pop()
    except KeyError:
        return False

    _remove_island(land_points, (x - 1, y))
    _remove_island(land_points, (x + 1, y))
    _remove_island(land_points, (x, y - 1))
    _remove_island(land_points, (x, y + 1))

    return True

if __name__ == '__main__':
    grid = dedent("""\
    11000
    11000
    00100
    00011""")

    print(count_islands(grid))

This aggressively refactored version could look roughly like this:

from textwrap import dedent
from typing import Iterable, List, NamedTuple, Optional, Set


class Point(NamedTuple('Point', [('x', int), ('y', int)])):
    @property
    def neighbors(self) -> Iterable['Point']:
        yield Point(self.x, self.y - 1)
        yield Point(self.x - 1, self.y)
        yield Point(self.x + 1, self.y)
        yield Point(self.x, self.y + 1)


class Grid(NamedTuple('Grid', [('rows', List[str])])):
    @classmethod
    def parse(cls, grid: str) -> 'Grid':
        rows = grid.splitlines()
        assert len(set(map(len, rows))), 'number of columns inconsistent'

        return cls(rows)

    @property
    def land_points(self) -> Iterable[Point]:
        for y, row in enumerate(self.rows):
            for x, col in enumerate(row):
                if col == '1':
                    yield Point(x, y)


class LandPointSet(set):
    def remove_any_island(self) -> bool:
        return self._remove_island_containing(None)

    def _remove_island_containing(self, point: Optional[Point]) -> None:
        try:
            if point:
                self.remove(point)
            else:
                point = self.pop()
        except KeyError:
            return False

        for neighbor in point.neighbors:
            self._remove_island_containing(neighbor)

        return True


def count_islands(grid: Grid):
    """
    Counts the number of contiguous islands in a grid.
    """

    land_points = LandPointSet(grid.land_points)

    # Remove islands until there are none left
    num_islands = 0
    while land_points.remove_any_island():
        num_islands += 1

    return num_islands


if __name__ == '__main__':
    grid = dedent("""\
    11000
    11000
    00100
    00011""")

    print(count_islands(Grid.parse(grid)))

Watch out for the recursion. Python's recursion limit could bite you depending on the size of an island. To avoid this, it's pretty easy to rewrite the removal iteratively using a set.