Find the number of non-contiguous islands in a 2d matrix world

Using recursion and depth-first search to find all islands in a given 2d matrix world

Mon Mar 16 2020

A really common algorithm asked in interviews is finding islands in a 2-dimensional matrix such as below.

# World with 2 islands, 1 huge and 1 tiny
world_1 = [

You can find the number of islands with the following algorithm

  • Scan the world, the easy solution is just column by column, row by row
  • If an island is encountered there is likely to be more land next to it in the directions N,S,E,W. Destroy the landmass by marking the contiguous elements as "0". Once the entire island is destroyed tally this island as one new island found.
  • Repeat
  • Return the number of new islands found in the tally

Hint: By destroying each island you arrive at, you never accidentally count parts of the same island as a new island

Python code

This code passes all tests in LeetCode


class Solution:
    """ Wrapper for LeetCode Solution """

    def numIslands(self, grid: [[str]]) -> int:
        Determines the number of islands in a matrix, before destroying them

        # World is empty, no land or water
        if not grid or not grid[0]:
            return 0

        islands_found = 0

        for row_index, row in enumerate(grid):
            for col_index, _col in enumerate(row):
                # if the current position is an island
                if grid[row_index][col_index] == "1":

                    # Mark island as found
                    islands_found += 1

                    # Destory entire island
                    self._destroy_island(grid, row_index, col_index)

        return islands_found

    def _destroy_island(self, grid: [[str]], row_index: int, col_index: int):
        """ Destroys the entire island """

        out_of_bounds_longitude = col_index < 0 or col_index >= len(grid[0])
        out_of_bounds_latitude = row_index < 0 or row_index >= len(grid)

        if out_of_bounds_longitude or out_of_bounds_latitude:

        current_position = grid[row_index][col_index]
        if current_position == "0":

        # Destroy island underneath the current position
        grid[row_index][col_index] = "0"

        # Destroy contigious island landmass to the north, south, east and west
        self._destroy_island(grid, row_index-1, col_index)
        self._destroy_island(grid, row_index+1, col_index)
        self._destroy_island(grid, row_index, col_index-1)
        self._destroy_island(grid, row_index, col_index+1)

Debugging and run code

def main():
    """ The entry point of the python script """

    world_1 = [

    sln = Solution()
    number_of_islands_world_1 = sln.numIslands(world_1)
    print(f"Number of islands destroyed in world_1: {number_of_islands_world_1}")

if __name__ == "__main__":
Paul Ness

Paul S. Ness Software engineer with ten years of experience in a variety of industries such travel, payments, medical, fine art and publishing.