:orphan:

Number of Islands
=================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/number-of-islands/

Given an ``m x n`` 2D binary grid ``grid`` which represents a map of
``'1'``\ s (land) and ``'0'``\ s (water), return *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.

 

**Example 1:**

::


   Input: grid = [
     ["1","1","1","1","0"],
     ["1","1","0","1","0"],
     ["1","1","0","0","0"],
     ["0","0","0","0","0"]
   ]
   Output: 1

**Example 2:**

::


   Input: grid = [
     ["1","1","0","0","0"],
     ["1","1","0","0","0"],
     ["0","0","1","0","0"],
     ["0","0","0","1","1"]
   ]
   Output: 3

 

**Constraints:**

- ``m == grid.length``
- ``n == grid[i].length``
- ``1 <= m, n <= 300``
- ``grid[i][j]`` is ``'0'`` or ``'1'``.

.. highlight:: python

Pattern
-------
Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Approaches
----------

.. tab-set::

    .. tab-item:: BFS

        **Code**

        .. literalinclude:: ../problems/medium/number-of-islands/number_of_islands__bfs.py
            :language: python
            :lines: 9-

        **Test**

        >>> from number_of_islands__bfs import numIslands
        >>> numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]])
        1
        >>> numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]])
        3

        .. autofunction:: number_of_islands__bfs.numIslands