> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/dfs-bfs/0200.-number-of-islands.md).

# 0200. Number of Islands

Medium  |  BFS + DFS  |  128 ms (94.03%),  15.2 MB (95.17%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Number of Islands](https://leetcode.com/problems/number-of-islands/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0200-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.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 300`
* `grid[i][j]` is `'0'` or `'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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
We could solve this problem by **either DFS or BFS method.**\
*(BFS requires less memory usage)*
{% endhint %}

> **DFS**

We **recursively explore** the whole map subject to the **boundary condition** for moving up, down, left, and right and **whether the current location is an island or not.**

> **BFS**

We **iteratively explore** the whole map by using a **stack to record the visited island** subject to the **boundary condition** for moving up, down, left, and right and **whether the current location is an island or not.**
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # (base case)
        if len(grid) == 1 and len(grid[0]) == 1: return 1 if grid[0][0] == "1" else 0
        
        # ==================================================
        #  BFS                                             =
        # ==================================================
        # time  : O(nm)
        # space : O(min(n,m))
        
        x = len(grid[0])
        y = len(grid)
        
        ans = 0
        
        for i in range(y):
            for j in range(x):
                if grid[i][j] == '1':
                    ans += 1
                    
                    visited = set()
                    visited.add( (i, j) )
                    
                    while visited:
                        row, col = visited.pop()
                        grid[row][col] = '0'
                        
                        if row   > 0 and grid[row-1][col] == '1': visited.add( (row-1, col) )
                        if row+1 < y and grid[row+1][col] == '1': visited.add( (row+1, col) )
                        if col   > 0 and grid[row][col-1] == '1': visited.add( (row, col-1) )
                        if col+1 < x and grid[row][col+1] == '1': visited.add( (row, col+1) )
                            
        return ans
        
    '''
    def numIslands(self, grid: List[List[str]]) -> int:
        # (base case)
        if len(grid) == 1 and len(grid[0]) == 1: return 1 if grid[0][0] == "1" else 0
        
        # ==================================================
        #  DFS                                             =
        # ==================================================
        # time  : O(mn)
        # space : O(mn)

        island = 0
        self.grid = grid
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1': 
                    self.explore(i, j)
                    island += 1
        
        return island
        
    def explore(self, y: int, x: int) -> None:
        self.grid[y][x] = 0
        
        if y > 0                     and self.grid[y-1][x] == '1': self.explore(y-1, x)
        if y < len(self.grid) - 1    and self.grid[y+1][x] == '1': self.explore(y+1, x)
        if x > 0                     and self.grid[y][x-1] == '1': self.explore(y, x-1)
        if x < len(self.grid[0]) - 1 and self.grid[y][x+1] == '1': self.explore(y, x+1)
    '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(nm)
     * @space : O(nm)
     */
    
    char[][] map;

    public int numIslands(char[][] grid) {
        int count = 0;
        
        map = grid;
        
        for(int i=0 ; i<grid.length ; i++) {
            for(int j=0 ; j<grid[0].length ; j++) {
                if(grid[i][j] == '1') {
                    count++;
                    explore(i, j);
                }
            }
        }
        
        return count;
    }
    
    public void explore(int x, int y) {
        if(x<0 || y<0 || x>= map.length || y>= map[0].length) {
            return;
        }
        
        if(map[x][y] == '0') {
            return;
        }
        
        map[x][y] = '0';
        
        explore(x-1, y);
        explore(x+1, y);
        explore(x,   y-1);
        explore(x,   y+1);
        
        return;
    }
}
```

{% endtab %}
{% endtabs %}