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

# Number of Islands

## Problem

Given an `m x n` 2d `grid` 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.

**Constraints:**

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

{% hint style="info" %}
For example:

```
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
```

{% endhint %}

### Thought Process

* DFS is a good approach since we are dealing with connected components as well as neighboring cells and switching/marking the visited components

* Our DFS cycle will break once we are out of bounds or come across a element that is not a '1'

* We are utilizing DFS to change/mark the visited cells and recurssing on its neighboring cells

## Solution

```
#Time: O(m*n) since we are traversing the whole matrix
#Space: O(m*n) for the recursion stack b/c worst case if we have all 1's
#then it's like s snak pattern in terms of stack calls

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    count+=1
                    self.dfsearch(grid,i,j)
                else:
                    continue
        return count
                    
        
    def dfsearch(self, grid, i, j):
        if i < 0 or i >= len(grid) or j >= len(grid[0]) or j < 0 or grid[i][j] != '1':
            return
        
        grid[i][j] = '0'
        
        self.dfsearch(grid,i+1,j)
        self.dfsearch(grid,i-1,j)
        self.dfsearch(grid,i,j-1)
        self.dfsearch(grid,i,j+1)
        
```

## Time Complexity

* **Time:** O(m\*n) since we are traversing the whole matrix
* **Space:** O(m\*n) for the recursion stack b/c worst case if we have all 1's then it's like a snake pattern in terms of stack calls